{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Maze III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #array #string #matrix #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #数组 #字符串 #矩阵 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findShortestWay"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #迷宫 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>由空地和墙组成的迷宫中有一个<strong>球</strong>。球可以向<strong>上（u）下（d）左（l）右（r）</strong>四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。迷宫中还有一个<strong>洞</strong>，当球运动经过洞时，就会掉进洞里。</p>\n",
    "\n",
    "<p>给定球的<strong>起始位置，目的地</strong>和<strong>迷宫</strong>，找出让球以最短距离掉进洞里的路径。&nbsp;距离的定义是球从起始位置（不包括）到目的地（包括）经过的<strong>空地</strong>个数。通过&#39;u&#39;, &#39;d&#39;, &#39;l&#39; 和&nbsp;&#39;r&#39;输出球的移动<strong>方向</strong>。&nbsp;由于可能有多条最短路径，&nbsp;请输出<strong>字典序最小</strong>的路径<strong>。</strong>如果球无法进入洞，输出&quot;impossible&quot;。</p>\n",
    "\n",
    "<p>迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例1:</strong></p>\n",
    "\n",
    "<pre><strong>输入 1:</strong> 迷宫由以下二维数组表示\n",
    "\n",
    "0 0 0 0 0\n",
    "1 1 0 0 1\n",
    "0 0 0 0 0\n",
    "0 1 0 0 1\n",
    "0 1 0 0 0\n",
    "\n",
    "<strong>输入 2:</strong> 球的初始位置 (rowBall, colBall) = (4, 3)\n",
    "<strong>输入 3:</strong> 洞的位置 (rowHole, colHole) = (0, 1)\n",
    "\n",
    "<strong>输出:</strong> &quot;lul&quot;\n",
    "\n",
    "<strong>解析:</strong> 有两条让球进洞的最短路径。\n",
    "第一条路径是 左 -&gt; 上 -&gt; 左, 记为 &quot;lul&quot;.\n",
    "第二条路径是 上 -&gt; 左, 记为 &#39;ul&#39;.\n",
    "两条路径都具有最短距离6, 但&#39;l&#39; &lt; &#39;u&#39;，故第一条路径字典序更小。因此输出&quot;lul&quot;。\n",
    "<img src=\"https://assets.leetcode.com/uploads/2018/10/13/maze_2_example_1.png\" style=\"width: 100%;\">\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre><strong>输入 1:</strong> 迷宫由以下二维数组表示\n",
    "\n",
    "0 0 0 0 0\n",
    "1 1 0 0 1\n",
    "0 0 0 0 0\n",
    "0 1 0 0 1\n",
    "0 1 0 0 0\n",
    "\n",
    "<strong>输入 2:</strong> 球的初始位置 (rowBall, colBall) = (4, 3)\n",
    "<strong>输入 3:</strong> 洞的位置 (rowHole, colHole) = (3, 0)\n",
    "\n",
    "<strong>输出:</strong> &quot;impossible&quot;\n",
    "\n",
    "<strong>示例:</strong> 球无法到达洞。\n",
    "<img src=\"https://assets.leetcode.com/uploads/2018/10/13/maze_2_example_2.png\" style=\"width: 100%;\">\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意:</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>迷宫中只有一个球和一个目的地。</li>\n",
    "\t<li>球和洞都在空地上，且初始时它们不在同一位置。</li>\n",
    "\t<li>给定的迷宫不包括边界 (如图中的红色矩形), 但你可以假设迷宫的边缘都是墙壁。</li>\n",
    "\t<li>迷宫至少包括2块空地，行数和列数均不超过30。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-maze-iii](https://leetcode.cn/problems/the-maze-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-maze-iii](https://leetcode.cn/problems/the-maze-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]]\\n[4,3]\\n[0,1]', '[[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]]\\n[4,3]\\n[3,0]', '[[0,0,0,0,0,0,0],[0,0,1,0,0,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,1]]\\n[0,4]\\n[3,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        def valid(row, col):\n",
    "            return 0 <= row < m and 0 <= col < n and maze[row][col] == 0\n",
    "\n",
    "        def get_neighbors(row, col):\n",
    "            directions = [(0, -1, 'l'), (-1, 0, 'u'), (0, 1, 'r'), (1, 0, 'd')]\n",
    "            neighbors = []\n",
    "\n",
    "            for dy, dx, direction in directions:\n",
    "                curr_row = row\n",
    "                curr_col = col\n",
    "                dist = 0\n",
    "                while valid(curr_row + dy, curr_col + dx):\n",
    "                    curr_row += dy\n",
    "                    curr_col += dx\n",
    "                    dist += 1\n",
    "                    if [curr_row, curr_col] == hole:\n",
    "                        break\n",
    "                neighbors.append((curr_row, curr_col, dist, direction))\n",
    "            return neighbors\n",
    "\n",
    "        m = len(maze)\n",
    "        n = len(maze[0])\n",
    "        heap = [(0, \"\", ball[0], ball[1])]\n",
    "        seen = {(ball[0], ball[1]):(0, \"\")}\n",
    "        while heap:\n",
    "            curr_dist, path, row, col = heappop(heap)\n",
    "            # if (row, col) in seen:\n",
    "            #     continue\n",
    "            if [row, col] == hole:\n",
    "                return path\n",
    "            # seen.((row, col))\n",
    "            for next_row, next_col, dist, direction in get_neighbors(row, col):\n",
    "                if (next_row, next_col) not in seen or (curr_dist + dist, path + direction) < seen[(next_row, next_col)]:\n",
    "                    seen[(next_row, next_col)] = (curr_dist + dist, path + direction)\n",
    "                    heappush(heap, (curr_dist + dist, path + direction, next_row, next_col))\n",
    "        return \"impossible\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "                                                    \n",
    "        directions = [(-1,0,'u'),(0,1,'r'),(0,-1,'l'),(1,0,'d')]    \n",
    "                                                    # 定义上下左右四个方向和对应字符\n",
    "        m = len(maze)                               # 获取矩阵大小\n",
    "        n = len(maze[0])\n",
    "        queue = [(ball[0],ball[1])]                 # 构造队列，并将起始位置包含其中\n",
    "                                                    # distance 保存从起点到每个点的距离\n",
    "                                                    # string 保存每个点对应的字符串\n",
    "        distance = [[float('inf')]*n for _ in range(m)]\n",
    "        string = [[\"impossible\"]*n for _ in range(m)]\n",
    "        distance[ball[0]][ball[1]] = 0              # 对起点的distance和string进行初始化\n",
    "        string[ball[0]][ball[1]] = \"\"\n",
    "\n",
    "        while queue:\n",
    "            i,j = queue.pop(0)                      # 弹出坐标值i,j\n",
    "            \n",
    "            for dx,dy,letter in directions:         # 对四个方向进行遍历，letter保存了操作对应的字符\n",
    "                x,y,step,word =i+dx,j+dy,distance[i][j],string[i][j]\n",
    "                while 0<=x<m and 0<=y<n and maze[x][y] == 0 and (x-dx!=hole[0] or y-dy!=hole[1]):                                      \n",
    "                                                    # 当x,y坐标合法，并且对应值为0\n",
    "                                                    # 且没有越过hole时\n",
    "                    x = x+dx                        # 继续前进，模拟小球的滚动过程\n",
    "                    y = y+dy                        \n",
    "                    step += 1                       # 记录步数\n",
    "\n",
    "                x = x - dx\n",
    "                y = y - dy\n",
    "\n",
    "                if distance[x][y] > step or (distance[x][y]==step and word+letter<string[x][y]):           \n",
    "                                                    # 如果起点到该点的距离比当前距离大\n",
    "                                                    # 或者相等，但是字符串的字典序大\n",
    "                                                    # 更新该距离和字符串，并将坐标加入队列\n",
    "                    distance[x][y] = step\n",
    "                    string[x][y] = word+letter\n",
    "                    #print(x,y,string[x][y])   \n",
    "                    if x!=hole[0] or y!=hole[1]:    # 当坐标不是hole坐标时\n",
    "                        queue.append((x,y))         # 将其添加到队列中\n",
    "                                           \n",
    "        return string[hole[0]][hole[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        ROWS = len(maze)\n",
    "        COLS = len(maze[0])\n",
    "        def roll(x, y):\n",
    "            def hitBoundry(x, y):\n",
    "                if not (0 <= x < ROWS and 0 <= y < COLS):\n",
    "                    return True\n",
    "                return maze[x][y] == 1\n",
    "            def rollBydirection(x, y, dx, dy):\n",
    "                while not hitBoundry(x + dx, y + dy):\n",
    "                    x += dx \n",
    "                    y += dy\n",
    "                    if [x, y] == hole:\n",
    "                        break\n",
    "                return x, y \n",
    "            directions = [('d', 1, 0), ('l', 0, -1), ('u', -1, 0), ('r', 0, 1)]\n",
    "            for ins, dx, dy in directions:\n",
    "                nx, ny = rollBydirection(x, y, dx, dy)\n",
    "                yield nx, ny, ins\n",
    "        PQ = [[0, \"\", ball[0], ball[1]]]\n",
    "        visited = set()\n",
    "        while PQ:\n",
    "            steps, instructions, curX, curY = heapq.heappop(PQ)\n",
    "            if [curX, curY] == hole:\n",
    "                return instructions\n",
    "            if (curX, curY) in visited:\n",
    "                continue\n",
    "            visited.add((curX, curY))\n",
    "            for nextX, nextY, nextIns in roll(curX, curY):\n",
    "                # print(curX, curY, nextX, nextY, nextIns)\n",
    "                nextInstructions = instructions + nextIns\n",
    "                nextSteps = abs(curX-nextX) + abs(curY-nextY)\n",
    "                heapq.heappush(PQ, [steps + nextSteps, nextInstructions, nextX, nextY])\n",
    "        return \"impossible\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        dirs = {'u':(-1, 0), 'd':(1, 0), 'l':(0, -1), 'r':(0, 1)}\n",
    "        pq = []\n",
    "        heapq.heapify(pq)\n",
    "        heapq.heappush(pq, (0, '', (ball[0], ball[1])))\n",
    "        dist = dict()\n",
    "        n = len(maze)\n",
    "        m = len(maze[0])\n",
    "        while pq:\n",
    "            node_dist, traj, node = heapq.heappop(pq)\n",
    "            row = node[0]\n",
    "            col = node[1]\n",
    "            if node in dist:\n",
    "                continue\n",
    "            if row == hole[0] and col == hole[1]:\n",
    "                return traj\n",
    "            dist[node] = (node_dist, traj)\n",
    "            for inst, direc in dirs.items():\n",
    "                edge_len = 1\n",
    "                r_direc = direc[0]\n",
    "                c_direc = direc[1]\n",
    "                n_row = row + r_direc\n",
    "                n_col = col + c_direc\n",
    "                while 0 <= n_row < n and 0 <= n_col < m and maze[n_row][n_col] != 1:\n",
    "                    if n_row == hole[0] and n_col == hole[1]:       \n",
    "                        heapq.heappush(pq, (node_dist + edge_len, traj + inst, (n_row, n_col)))\n",
    "                    edge_len += 1\n",
    "                    n_row += r_direc\n",
    "                    n_col += c_direc\n",
    "                n_row -= r_direc\n",
    "                n_col -= c_direc\n",
    "                edge_len -= 1\n",
    "                heapq.heappush(pq, (node_dist + edge_len, traj + inst, (n_row, n_col)))\n",
    "        return 'impossible'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        dirs=[[-1,0,'u'],[0,1,'r'],[0,-1,'l'],[1,0,'d']]\n",
    "        que=[ [ ball[0],ball[1] ] ]\n",
    "        dist=[[float('inf')]*n for i in range(m)]\n",
    "        strs=[['impossible']*n for i in range(m)]\n",
    "        dist[ball[0]][ball[1]]=0#初始化\n",
    "        strs[ball[0]][ball[1]]=''\n",
    "        while que:\n",
    "            x,y=que.pop(0)\n",
    "            for dx,dy,ch in dirs:\n",
    "                x1,y1,step,word=x+dx,y+dy,dist[x][y],strs[x][y]\n",
    "                while 0<=x1<m and 0<=y1<n and maze[x1][y1]==0 and (x1-dx!=hole[0]or y1-dy!=hole[1]):\n",
    "                    x1+=dx\n",
    "                    y1+=dy\n",
    "                    step+=1\n",
    "                x1,y1=x1-dx,y1-dy\n",
    "                if dist[x1][y1]>step or (dist[x1][y1]==step and word+ch<strs[x1][y1]):\n",
    "                    dist[x1][y1]=step\n",
    "                    strs[x1][y1]=word+ch\n",
    "                    # if x!=hole[0] or y!=hole[1]:\n",
    "                    if x1!=hole[0]or y1!=hole[1]:\n",
    "                        que.append([x1,y1])\n",
    "        return strs[hole[0]][hole[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        directions = {\n",
    "            \"l\": [0, -1],\n",
    "            \"r\": [0, 1],\n",
    "            \"d\": [1, 0],\n",
    "            \"u\": [-1, 0]\n",
    "        }\n",
    "        m = len(maze)\n",
    "        n = len(maze[0])\n",
    "        \n",
    "        def check(x, y):\n",
    "            return 0 <= x < m and 0 <= y < n and not maze[x][y]\n",
    "        ans = \"z\"\n",
    "        stack = [[ball[0], ball[1], d] for d in directions if check(ball[0] + directions[d][0], ball[1] + directions[d][1])]\n",
    "        visit = collections.defaultdict(set)\n",
    "        while stack and ans == \"z\":\n",
    "            nex = []\n",
    "            for x, y, path in stack:\n",
    "                visit[(x, y)].add(path[-1])\n",
    "            for x, y, path in stack:\n",
    "                if [x, y] == hole:\n",
    "                    ans = min(ans, path)\n",
    "                    continue\n",
    "                a, b = x + directions[path[-1]][0], y + directions[path[-1]][1]\n",
    "                if check(a, b):\n",
    "                    if path[-1] not in visit[(a, b)]:\n",
    "                        nex.append([a, b, path])\n",
    "                else:\n",
    "                    for d in directions:\n",
    "                        if d != path[-1]:\n",
    "                            a, b = x + directions[d][0], y + directions[d][1]\n",
    "                            if check(a, b) and d not in visit[(a, b)]:\n",
    "                                nex.append([a, b, path + d])\n",
    "            stack = nex\n",
    "        return ans if ans != \"z\" else \"impossible\"\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        pq = []\n",
    "        m,n = len(maze),len(maze[0])\n",
    "        heapq.heappush(pq, (0,'',ball[0],ball[1])) # 按照距离+字典序排序\n",
    "        dirs = {'u':(-1,0),'d':(1,0),'l':(0,-1),'r':(0,1)}\n",
    "        dis = [[inf]*n for _ in range(m)]\n",
    "        path = [['impossible']*n for _ in range(m)] # 这里初始化无所谓，dis不是inf的肯定path被修改过\n",
    "        path[ball[0]][ball[1]] = ''\n",
    "        dis[ball[0]][ball[1]] = 0\n",
    "        while pq:\n",
    "            s,p,x,y = heapq.heappop(pq)\n",
    "            if s > dis[x][y]:\n",
    "                continue\n",
    "            for d in ('u','d','l','r'):\n",
    "                r,c = dirs[d]\n",
    "                nx,ny = x,y\n",
    "                cnt = 0\n",
    "                while 0 <= nx + r < m and 0 <= ny + c < n and maze[nx + r][ny + c] == 0:\n",
    "                    nx += r\n",
    "                    ny += c\n",
    "                    cnt += 1\n",
    "                    if [nx,ny] == hole:\n",
    "                        break\n",
    "                    \n",
    "                if dis[nx][ny] > s + cnt or (dis[nx][ny] == s + cnt and p + d < path[nx][ny]):\n",
    "                    dis[nx][ny] = s + cnt\n",
    "                    path[nx][ny] = p + d\n",
    "                    if [nx,ny] != hole:\n",
    "                        heapq.heappush(pq,(s + cnt,path[nx][ny],nx,ny))\n",
    "        return path[hole[0]][hole[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "                                                    \n",
    "        directions = [(-1,0,'u'),(0,1,'r'),(0,-1,'l'),(1,0,'d')]    \n",
    "                                                    # 定义上下左右四个方向和对应字符\n",
    "        m = len(maze)                               # 获取矩阵大小\n",
    "        n = len(maze[0])\n",
    "        queue = [(ball[0],ball[1])]                 # 构造队列，并将起始位置包含其中\n",
    "                                                    # distance 保存从起点到每个点的距离\n",
    "                                                    # string 保存每个点对应的字符串\n",
    "        distance = [[float('inf')]*n for _ in range(m)]\n",
    "        string = [[\"impossible\"]*n for _ in range(m)]\n",
    "        distance[ball[0]][ball[1]] = 0              # 对起点的distance和string进行初始化\n",
    "        string[ball[0]][ball[1]] = \"\"\n",
    "\n",
    "        while queue:\n",
    "            i,j = queue.pop(0)                      # 弹出坐标值i,j\n",
    "            \n",
    "            for dx,dy,letter in directions:         # 对四个方向进行遍历，letter保存了操作对应的字符\n",
    "                x,y,step,word =i+dx,j+dy,distance[i][j],string[i][j]\n",
    "                while 0<=x<m and 0<=y<n and maze[x][y] == 0 and (x-dx!=hole[0] or y-dy!=hole[1]):                                      \n",
    "                                                    # 当x,y坐标合法，并且对应值为0\n",
    "                                                    # 且没有越过hole时\n",
    "                    x = x+dx                        # 继续前进，模拟小球的滚动过程\n",
    "                    y = y+dy                        \n",
    "                    step += 1                       # 记录步数\n",
    "\n",
    "                x = x - dx\n",
    "                y = y - dy\n",
    "\n",
    "                if distance[x][y] > step or (distance[x][y]==step and word+letter<string[x][y]):           \n",
    "                                                    # 如果起点到该点的距离比当前距离大\n",
    "                                                    # 或者相等，但是字符串的字典序大\n",
    "                                                    # 更新该距离和字符串，并将坐标加入队列\n",
    "                    distance[x][y] = step\n",
    "                    string[x][y] = word+letter\n",
    "                    #print(x,y,string[x][y])   \n",
    "                    if x!=hole[0] or y!=hole[1]:    # 当坐标不是hole坐标时\n",
    "                        queue.append((x,y))         # 将其添加到队列中\n",
    "                                           \n",
    "        return string[hole[0]][hole[1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze:List[List[int]],ball:List[int],hole:List[int])->str:\n",
    "        INF=0x3f3f3f3f\n",
    "        dr=[1,0,0,-1]            #水平方向偏移量\n",
    "        dc=[0,-1,1,0]            #垂直方向偏移量\n",
    "        dirstr=[\"d\",\"l\",\"r\",\"u\"]    #方位：字典序最小\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        qu=deque()      #定义队列，元素为[r,c]\n",
    "        dist=[[INF for _ in range(n)] for _ in range(m)]\n",
    "        path=[[\"\" for _ in range(n)] for _ in range(m)]\n",
    "        dist[ball[0]][ball[1]]=0\n",
    "        qu.append([ball[0],ball[1]])\n",
    "        while qu:\n",
    "            [r,c]=qu.popleft()\n",
    "            for di in range(0,4):  #从(r,c)扩展\n",
    "                nr,nc=r,c\n",
    "                delta=0\n",
    "                while nr+dr[di]>=0 and nr+dr[di]<m and \\\n",
    "                    nc+dc[di]>=0 and nc+dc[di]<n and \\\n",
    "                    maze[nr+dr[di]][nc+dc[di]]==0:  #一直滚下去\n",
    "                    nr,nc=nr+dr[di],nc+dc[di]       #按di方向滚到(nr,nc)\n",
    "                    delta+=1\n",
    "                    if nr==hole[0] and nc==hole[1]:\n",
    "                        break                  #找到洞时将其作为停靠点\n",
    "                curdist=dist[r][c]+delta\n",
    "                curpath=path[r][c]+dirstr[di]\n",
    "                if curdist<dist[nr][nc]:         #比较求最短路径\n",
    "                    dist[nr][nc]=curdist\n",
    "                    path[nr][nc]=curpath\n",
    "                    qu.append([nr,nc])\n",
    "                elif curdist==dist[nr][nc]:   #相同长度时\n",
    "                    if curpath<path[nr][nc]:\n",
    "                        path[nr][nc]=curpath\n",
    "                        qu.append([nr,nc])\n",
    "        if dist[hole[0]][hole[1]]==INF:return \"impossible\"\n",
    "        else:return path[hole[0]][hole[1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        q = collections.deque()\n",
    "        q.append(ball)\n",
    "        dist = [[float('inf')] * n for _ in range(m)]\n",
    "        dist[ball[0]][ball[1]] = 0\n",
    "        path = [['impossible'] * n for _ in range(m)]\n",
    "        path[ball[0]][ball[1]] = ''\n",
    "\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "\n",
    "            for dx, dy, d in [[0, 1, 'r'], [0, -1, 'l'], [1, 0, 'd'], [-1, 0, 'u']]:\n",
    "                nx, ny, step, p = x + dx, y + dy, dist[x][y] + 1, path[x][y] + d\n",
    "\n",
    "                while 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == 0 and not(nx - dx == hole[0] and ny - dy == hole[1]):\n",
    "                    nx += dx\n",
    "                    ny += dy\n",
    "                    step += 1\n",
    "                \n",
    "                nx -= dx\n",
    "                ny -= dy\n",
    "                step -= 1\n",
    "\n",
    "                if step < dist[nx][ny] or (step == dist[nx][ny] and p < path[nx][ny]):\n",
    "                    dist[nx][ny] = step\n",
    "                    path[nx][ny] = p\n",
    "                    if not (nx == hole[0] and ny == hole[1]):\n",
    "                        q.append([nx, ny])    \n",
    "\n",
    "        return path[hole[0]][hole[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        from collections import deque\n",
    "\n",
    "        m, n = len(maze), len(maze[0])\n",
    "\n",
    "        dirs = {'u': (-1, 0), 'd': (1, 0), 'l': (0, -1), 'r': (0, 1)}\n",
    "\n",
    "        dq = deque([ball])\n",
    "\n",
    "        distances = [[float('inf') for j in range(n)] for i in range(m)]\n",
    "        his_pathes = [['impossible' for j in range(n)] for i in range(m)]\n",
    "        distances[ball[0]][ball[1]] = 0\n",
    "        his_pathes[ball[0]][ball[1]] = \"\"\n",
    "        \n",
    "        while dq:\n",
    "            y, x = dq.popleft()\n",
    "           \n",
    "            for name, d in dirs.items():\n",
    "                cy, cx, dis, his_path = y, x, distances[y][x], his_pathes[y][x]\n",
    "                \n",
    "                while  m > cy + d[0] >= 0 and n > cx + d[1] >= 0  and maze[cy + d[0]][cx + d[1]] != 1 and (cy != hole[0] or cx !=hole[1]):\n",
    "                    cy = cy + d[0]\n",
    "                    cx = cx + d[1]\n",
    "                    dis += 1\n",
    "                \n",
    "                if distances[cy][cx] > dis or (dis == distances[cy][cx] and his_path + name < his_pathes[cy][cx]):\n",
    "                    distances[cy][cx] = dis\n",
    "                    his_pathes[cy][cx] = his_path + name\n",
    "                    if cy != hole[0] or cx != hole[1]:\n",
    "                        dq.append((cy, cx))\n",
    "            \n",
    "        return his_pathes[hole[0]][hole[1]]\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        m,n = len(maze),len(maze[0])\n",
    "        dir_map = {'u':(-1,0),'d':(1,0),'l':(0,-1),'r':(0,1)}\n",
    "        dis = [[inf]*n for _ in range(m)]\n",
    "        path = [['impossible']*n for _ in range(m)]\n",
    "        dis[ball[0]][ball[1]] = 0\n",
    "        path[ball[0]][ball[1]] = ''\n",
    "        q = []\n",
    "        heappush(q,(0,'',ball[0],ball[1]))\n",
    "        while q:\n",
    "            d,p,x,y = heappop(q)\n",
    "            if d > dis[x][y] or (d == dis[x][y] and p > path[x][y]):\n",
    "                continue\n",
    "            for dr in ('u','d','l','r'):\n",
    "                dx,dy = dir_map.get(dr)\n",
    "                nx,ny,step = x,y,0\n",
    "                while 0 <= nx + dx < m and 0 <= ny + dy < n and maze[nx + dx][ny + dy] == 0:\n",
    "                    nx += dx\n",
    "                    ny += dy\n",
    "                    step += 1\n",
    "                    if [nx,ny] == hole:\n",
    "                        break\n",
    "                if d + step < dis[nx][ny] or (d + step == dis[nx][ny] and p + dr < path[nx][ny]):\n",
    "                    dis[nx][ny] = d + step\n",
    "                    path[nx][ny] = p + dr\n",
    "                    if [nx,ny] != hole:\n",
    "                        heappush(q,(d + step,p + dr,nx,ny))\n",
    "        return path[hole[0]][hole[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class QNode:                    #优先队列结点类型\n",
    "    r,c=0,0\n",
    "    f,g,h=0,0,0\n",
    "    def __lt__(self,other):   #用于按f越小越优先出队\n",
    "        if self.f<other.f:return True\n",
    "        else:return False\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze:List[List[int]],ball:List[int],hole:List[int])->str:\n",
    "        INF=0x3f3f3f3f\n",
    "        dr=[1,0,0,-1]               #水平方向偏移量\n",
    "        dc=[0,-1,1,0]               #垂直方向偏移量\n",
    "        dirstr=[\"d\",\"l\",\"r\",\"u\"]    #方位：字典序最小\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        pqu=[]                      #定义小根堆，元素为QNode类型\n",
    "        e=QNode()\n",
    "        e.r,e.c=ball[0],ball[1]\n",
    "        e.g,e.h=0,self.geth(ball[0],ball[1],hole[0],hole[1])\n",
    "        e.f=e.g+e.h\n",
    "        heapq.heappush(pqu,e)\n",
    "        minf=[[INF for _ in range(n)] for _ in range(0,m)]\n",
    "        path=[[\"\" for _ in range(n)] for _ in range(0,m)]\n",
    "        minf[ball[0]][ball[1]]=0\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)\n",
    "            r,c=e.r,e.c\n",
    "            for di in range(0,4):  #从(r,c)扩展\n",
    "                nr,nc=r,c\n",
    "                delta=0\n",
    "                while nr+dr[di]>=0 and nr+dr[di]<m and \\\n",
    "                    nc+dc[di]>=0 and nc+dc[di]<n and \\\n",
    "                    maze[nr+dr[di]][nc+dc[di]]==0:  #一直滚下去\n",
    "                    nr,nc=nr+dr[di],nc+dc[di]       #按di方向滚到(nr,nc)\n",
    "                    delta+=1\t\t\t\t\t\t\t\t\t#走的空地数\n",
    "                    if nr==hole[0] and nc==hole[1]: \n",
    "                        break                     #找到洞时将其作为停靠点\n",
    "                e1=QNode()\n",
    "                e1.r,e1.c=nr,nc\n",
    "                e1.g=e.g+delta\n",
    "                e1.h=self.geth(nr,nc,hole[0],hole[1])\n",
    "                e1.f=e1.g+e1.h\n",
    "                curpath=path[r][c]+dirstr[di]\n",
    "                if e1.f<minf[nr][nc]:           #当前路径的f更短\n",
    "                    minf[nr][nc]=e1.f\n",
    "                    path[nr][nc]=curpath\n",
    "                    heapq.heappush(pqu,e1)\n",
    "                elif e1.f==minf[nr][nc]:            #f相同时\n",
    "                    if curpath<path[nr][nc]:      #取字段序比小的路径\n",
    "                        path[nr][nc]=curpath\n",
    "                        heapq.heappush(pqu,e1)\n",
    "        if path[hole[0]][hole[1]]==\"\":return \"impossible\"\n",
    "        else:return path[hole[0]][hole[1]]\n",
    "    def geth(self,x,y,gx,gy):       #计算启发式函数值\n",
    "        return abs(gx-x)+abs(gy-y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class QNode:                    #优先队列结点类型\n",
    "    r,c=0,0\n",
    "    f,g,h=0,0,0\n",
    "    def __lt__(self,other):   #用于按f越小越优先出队\n",
    "        if self.f<other.f:return True\n",
    "        else:return False\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze:List[List[int]],ball:List[int],hole:List[int])->str:\n",
    "        INF=0x3f3f3f3f\n",
    "        dr=[1,0,0,-1]               #水平方向偏移量\n",
    "        dc=[0,-1,1,0]               #垂直方向偏移量\n",
    "        dirstr=[\"d\",\"l\",\"r\",\"u\"]    #方位：字典序最小\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        pqu=[]                      #定义小根堆，元素为QNode类型\n",
    "        e=QNode()\n",
    "        e.r,e.c=ball[0],ball[1]\n",
    "        e.g,e.h=0,self.geth(ball[0],ball[1],hole[0],hole[1])\n",
    "        e.f=e.g+e.h\n",
    "        heapq.heappush(pqu,e)\n",
    "        minf=[[INF for _ in range(n)] for _ in range(0,m)]\n",
    "        path=[[\"\" for _ in range(n)] for _ in range(0,m)]\n",
    "        minf[ball[0]][ball[1]]=0\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)\n",
    "            r,c=e.r,e.c\n",
    "            for di in range(0,4):  #从(r,c)扩展\n",
    "                nr,nc=r,c\n",
    "                delta=0\n",
    "                while nr+dr[di]>=0 and nr+dr[di]<m and \\\n",
    "                    nc+dc[di]>=0 and nc+dc[di]<n and \\\n",
    "                    maze[nr+dr[di]][nc+dc[di]]==0:  #一直滚下去\n",
    "                    nr,nc=nr+dr[di],nc+dc[di]       #按di方向滚到(nr,nc)\n",
    "                    delta+=1\t\t\t\t\t\t\t\t\t#走的空地数\n",
    "                    if nr==hole[0] and nc==hole[1]: \n",
    "                        break                     #找到洞时将其作为停靠点\n",
    "                e1=QNode()\n",
    "                e1.r,e1.c=nr,nc\n",
    "                e1.g=e.g+delta\n",
    "                e1.h=self.geth(nr,nc,hole[0],hole[1])\n",
    "                e1.f=e1.g+e1.h\n",
    "                curpath=path[r][c]+dirstr[di]\n",
    "                if e1.f<minf[nr][nc]:           #当前路径的f更短\n",
    "                    minf[nr][nc]=e1.f\n",
    "                    path[nr][nc]=curpath\n",
    "                    heapq.heappush(pqu,e1)\n",
    "                elif e1.f==minf[nr][nc]:            #f相同时\n",
    "                    if curpath<path[nr][nc]:      #取字段序比小的路径\n",
    "                        path[nr][nc]=curpath\n",
    "                        heapq.heappush(pqu,e1)\n",
    "        if path[hole[0]][hole[1]]==\"\":return \"impossible\"\n",
    "        else:return path[hole[0]][hole[1]]\n",
    "    def geth(self,x,y,gx,gy):       #计算启发式函数值\n",
    "        return abs(gx-x)+abs(gy-y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        dirs = (('u', -1, 0), ('d', 1, 0), ('l', 0, -1), ('r', 0, 1))\n",
    "        pq = [(0, '', *ball)]\n",
    "        costs = defaultdict(lambda: 'z')\n",
    "        costs[tuple(ball)] = 'a'\n",
    "        best = set()\n",
    "        ans = []\n",
    "        while pq:\n",
    "            steps, cost, r, c = heappop(pq)\n",
    "            if [r, c] == hole:\n",
    "                return cost \n",
    "            best.add((r, c))\n",
    "            for d, dr, dc in dirs:\n",
    "                nr, nc = r, c\n",
    "                step = 0\n",
    "                while rows > nr >= 0 <= nc < cols and maze[nr][nc] == 0 and [nr, nc] != hole:\n",
    "                    nr += dr \n",
    "                    nc += dc \n",
    "                    step += 1\n",
    "                if [nr, nc] != hole:\n",
    "                    nr -= dr \n",
    "                    nc -= dc \n",
    "                    step -= 1\n",
    "                \n",
    "                if (nr, nc) not in best:\n",
    "                    nsteps = steps + step \n",
    "                    ncost = cost + d \n",
    "                    if ncost < costs[(nr, nc)]:\n",
    "                        costs[(nr, nc)] = ncost\n",
    "                        heappush(pq, (nsteps, ncost, nr, nc))\n",
    "        return 'impossible'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze:List[List[int]],ball:List[int],hole:List[int])->str:\n",
    "        INF=0x3f3f3f3f\n",
    "        dr=[1,0,0,-1]            #水平方向偏移量\n",
    "        dc=[0,-1,1,0]            #垂直方向偏移量\n",
    "        dirstr=[\"d\",\"l\",\"r\",\"u\"]    #方位：字典序最小\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        dist=[[INF for _ in range(n)] for _ in range(m)]\n",
    "        path=[[\"\" for _ in range(n)] for _ in range(m)]\n",
    "        S=[[False for _ in range(n)] for _ in range(m)]\n",
    "        pqu=[]                      #定义小根堆，元素为[steps,r,c]\n",
    "        heapq.heappush(pqu,[0,ball[0],ball[1]])\n",
    "        dist[ball[0]][ball[1]]=0\n",
    "        S[ball[0]][ball[1]]=True\n",
    "        while pqu:\n",
    "            [steps,r,c]=heapq.heappop(pqu)\n",
    "            S[r][c]=True                    #将(r,c)添加到S集合中\n",
    "            if r==hole[0] and c==hole[1]:   #一旦找到目的地则返回\n",
    "                return path[r][c]\n",
    "            for di in range(0,4):  #从(r,c)扩展\n",
    "                nr,nc=r,c\n",
    "                delta=0\n",
    "                while nr+dr[di]>=0 and nr+dr[di]<m and \\\n",
    "                    nc+dc[di]>=0 and nc+dc[di]<n and \\\n",
    "                    maze[nr+dr[di]][nc+dc[di]]==0:  #一直滚下去\n",
    "                    nr,nc=nr+dr[di],nc+dc[di]       #按di方向滚到(nr,nc)\n",
    "                    delta+=1\t\t\t\t\t\t\t\t\t#走的空地数\n",
    "                    if nr==hole[0] and nc==hole[1]: \n",
    "                        break                     #找到洞时将其作为停靠点\n",
    "                if S[nr][nc]:continue           #仅修改不在S中的位置\n",
    "                curdist=dist[r][c]+delta\n",
    "                curpath=path[r][c]+dirstr[di]\n",
    "                if curdist<dist[nr][nc]:          \t#比较求最短路径\n",
    "                    dist[nr][nc]=curdist\n",
    "                    path[nr][nc]=curpath\n",
    "                    heapq.heappush(pqu,[dist[nr][nc],nr,nc])\n",
    "                elif curdist==dist[nr][nc]:      #相同长度时\n",
    "                    if curpath<path[nr][nc]:\n",
    "                        path[nr][nc]=curpath\n",
    "                        heapq.heappush(pqu,[dist[nr][nc],nr,nc])\n",
    "        return \"impossible\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        directions = [(-1,0,'u'),(0,1,'r'),(0,-1,'l'),(1,0,'d')]  \n",
    "        m, n = len(maze), len(maze[0])\n",
    "        queue = [(ball[0], ball[1])]\n",
    "\n",
    "        dist = [[float('inf')]*n for _ in range(m)]\n",
    "        res = [['impossible']*n for _ in range(m)]\n",
    "        dist[ball[0]][ball[1]] = 0\n",
    "        res[ball[0]][ball[1]] = \"\"\n",
    "\n",
    "        while len(queue)>0:\n",
    "            i, j = queue.pop(0)\n",
    "\n",
    "            for dx, dy, dir in directions:\n",
    "                x, y, step, word = i+dx, j+dy, dist[i][j], res[i][j]\n",
    "                while 0<=x<m and 0<=y<n and maze[x][y]==0 and (x-dx!=hole[0] or y-dy!=hole[1]):\n",
    "                    x, y = x+dx, y+dy \n",
    "                    step += 1\n",
    "                x -= dx\n",
    "                y -= dy\n",
    "                if dist[x][y]>step or (dist[x][y]==step and word+dir<res[x][y]):\n",
    "                    dist[x][y] = step\n",
    "                    res[x][y] = word+dir\n",
    "                    if x!=hole[0] or y!=hole[1]:\n",
    "                        queue.append((x, y))\n",
    "        return res[hole[0]][hole[1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        Row, Col = len(maze), len(maze[0])\n",
    "        dist = [[float('inf') for _ in range(Col)] for _ in range(Row)]\n",
    "        path = [['impossible' for _ in range(Col)] for _ in range(Row)]\n",
    "\n",
    "        dist[ball[0]][ball[1]] = 0\n",
    "        path[ball[0]][ball[1]] = \"\"\n",
    "\n",
    "        Q = [(ball[0], ball[1])]\n",
    "        while Q:\n",
    "            r,c = Q.pop(0)\n",
    "            for dr,dc,direction in ((0,1,'r'), (1,0,'d'), (0,-1,'l'), (-1,0,'u')):\n",
    "                nr = r + dr\n",
    "                nc = c + dc\n",
    "                acc_step = dist[r][c] + 1\n",
    "                new_path = path[r][c] + direction\n",
    "                while 0 <= nr < Row and 0 <= nc < Col and maze[nr][nc] == 0 and not(nr-dr==hole[0] and nc-dc==hole[1]):#不能是从洞滚过来的\n",
    "                    nr += dr        #沿着这个方向继续前进\n",
    "                    nc += dc\n",
    "                    acc_step += 1\n",
    "                nr -= dr            #碰壁了，回退一步\n",
    "                nc -= dc\n",
    "                acc_step -= 1\n",
    "                if acc_step < dist[nr][nc] or (acc_step == dist[nr][nc] and new_path < path[nr][nc]):#或者字典序更小\n",
    "                    dist[nr][nc] = acc_step\n",
    "                    path[nr][nc] = new_path\n",
    "                    if not (nr == hole[0] and nc == hole[1]):   #进了洞，就不可能再滚动了\n",
    "                        Q.append( (nr,nc) )\n",
    "        \n",
    "        return path[hole[0]][hole[1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        stack = deque()\n",
    "        m,n = len(maze),len(maze[0])\n",
    "        memorization = [[float('inf') for i in range(n)] for i in range(m)]  \n",
    "        String = [[\"impossible\"]*n for _ in range(m)]\n",
    "        stack.append((ball[0],ball[1]))\n",
    "        String[ball[0]][ball[1]] = \"\"\n",
    "        memorization[ball[0]][ball[1]] = 0\n",
    "        direction = [(0,1,1,'r'),(0,-1,1,'l'),(1,0,1,'d'),(-1,0,1,'u')]\n",
    "        while(stack):\n",
    "            cur_r,cur_c = stack.popleft()\n",
    "            for r,c,length,_direction in direction:\n",
    "                new_r,new_c = cur_r+r,cur_c+c\n",
    "                new_length,new_path = memorization[cur_r][cur_c]+length,String[cur_r][cur_c]+_direction\n",
    "                while(0<=new_r<m and 0<=new_c<n and [new_r-r,new_c-c]!=hole and maze[new_r][new_c]!=1):\n",
    "                    new_r,new_c,new_length = new_r+r,new_c+c,new_length+length\n",
    "                new_r,new_c,new_length = new_r-r,new_c-c,new_length-length\n",
    "                if new_length<memorization[new_r][new_c] or (new_length==memorization[new_r][new_c] and new_path<String[new_r][new_c]):\n",
    "                    memorization[new_r][new_c] = new_length\n",
    "                    String[new_r][new_c] = new_path\n",
    "                    if new_r!=hole[0] or new_c!=hole[1]:\n",
    "                        stack.append((new_r,new_c))\n",
    "        \n",
    "        return String[hole[0]][hole[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        n, m = len(maze), len(maze[0])\n",
    "        q = collections.deque()\n",
    "        dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        d = [[math.inf for _ in range(m)] for _ in range(n)]\n",
    "        s = [[\"\" for _ in range(m)] for _ in range(n)]\n",
    "        d[ball[0]][ball[1]] = 0\n",
    "        move = \"udlr\"\n",
    "        q.append([ball[0], ball[1]])\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            dist = d[x][y]\n",
    "            state = s[x][y]\n",
    "            tmpx, tmpy, tmpdist = x, y, dist\n",
    "            for i, (dx, dy) in enumerate(dxy):\n",
    "                a, b = x + dx, y + dy\n",
    "                while a >= 0 and a < n and b >= 0 and b < m and maze[a][b] == 0 and [x, y] != hole:\n",
    "                    x, y = x + dx, y + dy\n",
    "                    a, b = x + dx, y + dy\n",
    "                    dist += 1\n",
    "                # 只有距离变小才更新\n",
    "                if d[x][y] > dist:\n",
    "                    d[x][y] = dist\n",
    "                    s[x][y] = state + move[i]\n",
    "                    q.append([x, y])\n",
    "                if d[x][y] == dist and s[x][y] > state + move[i]:\n",
    "                    s[x][y] = state + move[i]\n",
    "                    q.append([x, y])\n",
    "                x, y, dist = tmpx, tmpy, tmpdist\n",
    "        return \"impossible\" if d[hole[0]][hole[1]] == inf else s[hole[0]][hole[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        stack = deque()\n",
    "        m,n = len(maze),len(maze[0])\n",
    "        memorization = [[float('inf') for i in range(n)] for i in range(m)]  \n",
    "        String = [[\"impossible\"]*n for _ in range(m)]\n",
    "        stack.append((ball[0],ball[1]))\n",
    "        String[ball[0]][ball[1]] = \"\"\n",
    "        memorization[ball[0]][ball[1]] = 0\n",
    "        direction = [(0,1,1,'r'),(0,-1,1,'l'),(1,0,1,'d'),(-1,0,1,'u')]\n",
    "        while(stack):\n",
    "            cur_r,cur_c = stack.popleft()\n",
    "            for r,c,length,_direction in direction:\n",
    "                new_r,new_c = cur_r+r,cur_c+c\n",
    "                new_length,new_path = memorization[cur_r][cur_c]+length,String[cur_r][cur_c]+_direction\n",
    "                while(0<=new_r<m and 0<=new_c<n and [new_r-r,new_c-c]!=hole and maze[new_r][new_c]!=1):\n",
    "                    new_r,new_c,new_length = new_r+r,new_c+c,new_length+length\n",
    "                new_r,new_c,new_length = new_r-r,new_c-c,new_length-length\n",
    "                if new_length<memorization[new_r][new_c] or (new_length==memorization[new_r][new_c] and new_path<String[new_r][new_c]):\n",
    "                    memorization[new_r][new_c] = new_length\n",
    "                    String[new_r][new_c] = new_path\n",
    "                    if new_r!=hole[0] or new_c!=hole[1]:\n",
    "                        stack.append((new_r,new_c))\n",
    "        \n",
    "        return String[hole[0]][hole[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "\n",
    "                                                    \n",
    "\n",
    "        directions = [(-1,0,'u'),(0,1,'r'),(0,-1,'l'),(1,0,'d')]    \n",
    "\n",
    "                                                    # 定义上下左右四个方向和对应字符\n",
    "\n",
    "        m = len(maze)                               # 获取矩阵大小\n",
    "\n",
    "        n = len(maze[0])\n",
    "\n",
    "        queue = [(ball[0],ball[1])]                 # 构造队列，并将起始位置包含其中\n",
    "\n",
    "                                                    # distance 保存从起点到每个点的距离\n",
    "\n",
    "                                                    # string 保存每个点对应的字符串\n",
    "\n",
    "        distance = [[float('inf')]*n for _ in range(m)]\n",
    "\n",
    "        string = [[\"impossible\"]*n for _ in range(m)]\n",
    "\n",
    "        distance[ball[0]][ball[1]] = 0              # 对起点的distance和string进行初始化\n",
    "\n",
    "        string[ball[0]][ball[1]] = \"\"\n",
    "\n",
    "\n",
    "\n",
    "        while queue:\n",
    "\n",
    "            i,j = queue.pop(0)                      # 弹出坐标值i,j\n",
    "\n",
    "            \n",
    "\n",
    "            for dx,dy,letter in directions:         # 对四个方向进行遍历，letter保存了操作对应的字符\n",
    "\n",
    "                x,y,step,word =i+dx,j+dy,distance[i][j],string[i][j]\n",
    "\n",
    "                while 0<=x<m and 0<=y<n and maze[x][y] == 0 and (x-dx!=hole[0] or y-dy!=hole[1]):                                      \n",
    "\n",
    "                                                    # 当x,y坐标合法，并且对应值为0\n",
    "\n",
    "                                                    # 且没有越过hole时\n",
    "\n",
    "                    x = x+dx                        # 继续前进，模拟小球的滚动过程\n",
    "\n",
    "                    y = y+dy                        \n",
    "\n",
    "                    step += 1                       # 记录步数\n",
    "\n",
    "\n",
    "\n",
    "                x = x - dx\n",
    "\n",
    "                y = y - dy\n",
    "\n",
    "\n",
    "\n",
    "                if distance[x][y] > step or (distance[x][y]==step and word+letter<string[x][y]):           \n",
    "\n",
    "                                                    # 如果起点到该点的距离比当前距离大\n",
    "\n",
    "                                                    # 或者相等，但是字符串的字典序大\n",
    "\n",
    "                                                    # 更新该距离和字符串，并将坐标加入队列\n",
    "\n",
    "                    distance[x][y] = step\n",
    "\n",
    "                    string[x][y] = word+letter\n",
    "\n",
    "                    #print(x,y,string[x][y])   \n",
    "\n",
    "                    if x!=hole[0] or y!=hole[1]:    # 当坐标不是hole坐标时\n",
    "\n",
    "                        queue.append((x,y))         # 将其添加到队列中\n",
    "\n",
    "                                           \n",
    "\n",
    "        return string[hole[0]][hole[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze, ball, hole):\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        ball, hole = tuple(ball), tuple(hole)\n",
    "        \n",
    "        queue = [(0, ball, '')]\n",
    "        cloud = set([ball])\n",
    "        while queue:\n",
    "            path, node, directions = heappop(queue)\n",
    "            cloud.add(node)\n",
    "            if node == hole:\n",
    "                return directions\n",
    "            i, j = node[0], node[1]\n",
    "            for x, y, d in [(1,0,'d'),(-1,0,'u'),(0,1,'r'),(0,-1,'l')]:\n",
    "                ni, nj = i+x, j+y\n",
    "                count = 0\n",
    "                while 0<=ni<m and 0<=nj<n and maze[ni][nj]==0:\n",
    "                    if (ni,nj) == hole:\n",
    "                        ni, nj = ni+x, nj+y\n",
    "                        count += 1\n",
    "                        break\n",
    "                    else:\n",
    "                        ni, nj = ni+x, nj+y\n",
    "                        count += 1 \n",
    "                ni, nj = ni-x, nj-y\n",
    "                if (ni, nj) not in cloud:\n",
    "                    heappush(queue, (path+count, (ni, nj), directions+d))\n",
    "        return \"impossible\"\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        # bfs to find the shortest path \n",
    "        # point has 4 edge, each edge has a value \n",
    "        # in the bfs loops, use loop to find the next point  \n",
    "        m = len(maze)\n",
    "        n = len(maze[0])\n",
    "        directions = [(1, 0, 'd'), (0, 1, 'r'), (0, -1, 'l'),(-1, 0, 'u')]\n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        queue = [(0, ball, '')] # is a minheap\n",
    "        while queue:\n",
    "            poped = queue[0]\n",
    "            heapq.heappop(queue)\n",
    "            ori_dist = poped[0]\n",
    "            path = poped[2]\n",
    "            pop_x = poped[1][0]\n",
    "            pop_y = poped[1][1]\n",
    "            print(poped)\n",
    "            visited[pop_x][pop_y] = True\n",
    "\n",
    "            if pop_x == hole[0] and pop_y == hole[1]:\n",
    "                return path\n",
    "\n",
    "\n",
    "            for direction in directions:\n",
    "                x = poped[1][0]\n",
    "                y = poped[1][1]\n",
    "                dist = 0\n",
    "                ending = False\n",
    "                while True:\n",
    "                    if x < 0 or x >= m or y < 0 or y >=n:\n",
    "                        break\n",
    "\n",
    "                    if maze[x][y] == 1:\n",
    "                        break\n",
    "\n",
    "                    if x == hole[0] and y == hole[1]:\n",
    "                        # bingo \n",
    "                        x += direction[0]\n",
    "                        y += direction[1]\n",
    "                        dist += 1\n",
    "                        break\n",
    "\n",
    "                    x += direction[0]\n",
    "                    y += direction[1]\n",
    "                    dist += 1\n",
    "\n",
    "                newx = x - direction[0]\n",
    "                newy = y - direction[1]\n",
    "                dist -= 1\n",
    "\n",
    "                new_dist= ori_dist + dist\n",
    "\n",
    "                if newx == poped[1][0] and newy == poped[1][1]:\n",
    "                    # ignore this direction\n",
    "                    continue \n",
    "            \n",
    "                #print([newx, newy])\n",
    "\n",
    "\n",
    "                if not visited[newx][newy]:\n",
    "                    heapq.heappush(queue, (new_dist, [newx, newy], path + direction[2]))\n",
    "        \n",
    "\n",
    "        return \"impossible\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], start: List[int], destination: List[int]) -> str:\n",
    "      \n",
    "        row=len(maze)\n",
    "        col=len(maze[0])\n",
    "\n",
    "        #dijkstra\n",
    "        cost={}\n",
    "        pre={}\n",
    "        cost[(start[0],start[1])]=0\n",
    "        pre[(start[0],start[1])]=(start[0],start[1],\"\")\n",
    "        hp=[(0,start[0],start[1])]\n",
    "        dir=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        df={(0,1):\"r\",(0,-1):\"l\",(1,0):\"d\",(-1,0):\"u\"}\n",
    "        holecost=-1\n",
    "        while hp:\n",
    "            pcost,pr,pc=heapq.heappop(hp)\n",
    "            if holecost!=-1 and pcost>=holecost:\n",
    "                break\n",
    "            if cost[(pr,pc)]<pcost:\n",
    "                continue            \n",
    "            for offr,offc in dir:\n",
    "                nr=pr\n",
    "                nc=pc\n",
    "                ncost=-1\n",
    "                dw=pre[(pr,pc)][2]+df[(offr,offc)]\n",
    "                for c in range(1,max(col,row)+1):\n",
    "                    nc+=offc\n",
    "                    nr+=offr\n",
    "                    if [nr,nc]==destination:\n",
    "                        ncost=pcost+c                        \n",
    "                        update=False\n",
    "                        if (nr,nc) not in cost:\n",
    "                            update=True                          \n",
    "                        else:\n",
    "                            if cost[(nr,nc)]>ncost:\n",
    "                                update=True\n",
    "                            elif cost[(nr,nc)]==ncost:\n",
    "                                if pre[(nr,nc)][2]>dw:\n",
    "                                    update=True\n",
    "                        if update:\n",
    "                            cost[(nr,nc)]=ncost  \n",
    "                            holecost=ncost\n",
    "                            pre[(nr,nc)]=(pr,pc,dw)\n",
    "                        break\n",
    "                  \n",
    "                    if 0<=nc<col and 0<=nr<row and maze[nr][nc]==1:\n",
    "                        if c>1:\n",
    "                            ncost=pcost+c-1                             \n",
    "                        break\n",
    "                    if nr==-1 or nc==-1 or nr==row or nc==col:\n",
    "                        if c>1:\n",
    "                            ncost=pcost+c-1\n",
    "                        break \n",
    "                if ncost!=-1 and [nr,nc]!=destination:\n",
    "                    nc-=offc\n",
    "                    nr-=offr\n",
    "                    update=False\n",
    "                    if (nr,nc) not in cost:\n",
    "                        update=True                        \n",
    "                    else:\n",
    "                        if cost[(nr,nc)]>ncost:\n",
    "                            update=True\n",
    "                        elif cost[(nr,nc)]==ncost:\n",
    "                            if dw<pre[(nr,nc)][2]:\n",
    "                                update=True                           \n",
    "                    if update:\n",
    "                        cost[(nr,nc)]=ncost\n",
    "                        pre[(nr,nc)]=(pr,pc,dw)\n",
    "                        heapq.heappush(hp,(ncost,nr,nc))\n",
    "        if holecost==-1:\n",
    "            return \"impossible\"  \n",
    "        else:            \n",
    "            return pre[(destination[0],destination[1])][2]          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        pos = [(-1, 0, 'u'), (0, 1, 'r'), (0, -1, 'l'), (1, 0, 'd')]\n",
    "        q = deque()\n",
    "        q.append((ball[0], ball[1]))\n",
    "\n",
    "        dist = [[inf] * n for _ in range(m)]\n",
    "        words = [['impossible'] * n for _ in range(m)]\n",
    "        dist[ball[0]][ball[1]] = 0\n",
    "        words[ball[0]][ball[1]] = ''\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                i, j = q.popleft()\n",
    "                for dx, dy, c in pos:\n",
    "                    x, y, s, ans = i + dx, j + dy, dist[i][j], words[i][j]\n",
    "                    while 0 <= x < m and 0 <= y < n and maze[x][y] == 0 and (x - dx != hole[0] or y - dy != hole[1]):\n",
    "                        x += dx\n",
    "                        y += dy\n",
    "                        s += 1\n",
    "                    x -= dx\n",
    "                    y -= dy\n",
    "                    # s -= 1\n",
    "                    if dist[x][y] > s or (dist[x][y] == s and ans + c < words[x][y]):\n",
    "                        dist[x][y] = s \n",
    "                        words[x][y] = ans + c \n",
    "                        if x != hole[0] or y != hole[1]:\n",
    "                            q.append((x, y))\n",
    "        return words[hole[0]][hole[1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        directions = [(-1, 0, 'u'), (0, 1, 'r'), (0, -1, 'l'), (1, 0, 'd')]\n",
    "    # 定义上下左右四个方向和对应字符\n",
    "        m = len(maze)  # 获取矩阵大小\n",
    "        n = len(maze[0])\n",
    "        queue = [(ball[0], ball[1])]  # 构造队列，并将起始位置包含其中\n",
    "    # distance 保存从起点到每个点的距离\n",
    "    # string 保存每个点对应的字符串\n",
    "        distance = [[float('inf')] * n for _ in range(m)]\n",
    "        string = [[\"impossible\"] * n for _ in range(m)]\n",
    "        distance[ball[0]][ball[1]] = 0  # 对起点的distance和string进行初始化\n",
    "        string[ball[0]][ball[1]] = \"\"\n",
    "\n",
    "        while queue:\n",
    "            i, j = queue.pop(0)  # 弹出坐标值i,j\n",
    "\n",
    "            for dx, dy, letter in directions:  # 对四个方向进行遍历，letter保存了操作对应的字符\n",
    "                x, y, step, word = i + dx, j + dy, distance[i][j], string[i][j]\n",
    "                while 0 <= x < m and 0 <= y < n and maze[x][y] == 0 and (x - dx != hole[0] or y - dy != hole[1]):\n",
    "                # 当x,y坐标合法，并且对应值为0\n",
    "                # 且没有越过hole时\n",
    "                    x = x + dx  # 继续前进，模拟小球的滚动过程\n",
    "                    y = y + dy\n",
    "                    step += 1  # 记录步数\n",
    "\n",
    "                x = x - dx\n",
    "                y = y - dy\n",
    "\n",
    "                if distance[x][y] > step or (distance[x][y] == step and word + letter < string[x][y]):\n",
    "                # 如果起点到该点的距离比当前距离大\n",
    "                # 或者相等，但是字符串的字典序大\n",
    "                # 更新该距离和字符串，并将坐标加入队列\n",
    "                    distance[x][y] = step\n",
    "                    string[x][y] = word + letter\n",
    "                # print(x,y,string[x][y])\n",
    "                    if x != hole[0] or y != hole[1]:  # 当坐标不是hole坐标时\n",
    "                        queue.append((x, y))  # 将其添加到队列中\n",
    "\n",
    "        return string[hole[0]][hole[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        n, m = len(maze), len(maze[0])\n",
    "        q = collections.deque()\n",
    "        dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        d = [[math.inf for _ in range(m)] for _ in range(n)]\n",
    "        s = [[\"\" for _ in range(m)] for _ in range(n)]\n",
    "        d[ball[0]][ball[1]] = 0\n",
    "        move = \"udlr\"\n",
    "        q.append([ball[0], ball[1]])\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            dist = d[x][y]\n",
    "            state = s[x][y]\n",
    "            tmpx, tmpy, tmpdist = x, y, dist\n",
    "            for i, (dx, dy) in enumerate(dxy):\n",
    "                a, b = x + dx, y + dy\n",
    "                while a >= 0 and a < n and b >= 0 and b < m and maze[a][b] == 0 and [x, y] != hole:\n",
    "                    x, y = x + dx, y + dy\n",
    "                    a, b = x + dx, y + dy\n",
    "                    dist += 1\n",
    "                # 只有距离变小才更新\n",
    "                if d[x][y] > dist:\n",
    "                    d[x][y] = dist\n",
    "                    s[x][y] = state + move[i]\n",
    "                    q.append([x, y])\n",
    "                if d[x][y] == dist and s[x][y] > state + move[i]:\n",
    "                    s[x][y] = state + move[i]\n",
    "                    q.append([x, y])\n",
    "                x, y, dist = tmpx, tmpy, tmpdist\n",
    "        if d[hole[0]][hole[1]] == math.inf:\n",
    "            return \"impossible\" \n",
    "        return s[hole[0]][hole[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        \n",
    "        next_positions = dict()\n",
    "        next_positions['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    next_positions['l'][i][j] = end_left+1\n",
    "        next_positions['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    next_positions['r'][i][j] = end_right-1\n",
    "        next_positions['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    next_positions['u'][i][j] = end_up+1\n",
    "        next_positions['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    next_positions['d'][i][j] = end_down-1\n",
    "        \n",
    "        heap = [0]\n",
    "        length_positions = {0:{ball}}\n",
    "        position_length = {ball:0}\n",
    "        position_actions = {ball:''}\n",
    "        global min_length\n",
    "        min_length = 1e10\n",
    "\n",
    "        def get_next_position(position, action):\n",
    "            if action == 'd' or action == 'u':\n",
    "                return (next_positions[action][position[0]][position[1]], position[1])\n",
    "            else:\n",
    "                return (position[0], next_positions[action][position[0]][position[1]])\n",
    "        \n",
    "        def one_step(position, length, actions, next_action):\n",
    "            global min_length\n",
    "            next_position = get_next_position(position, next_action)\n",
    "            next_actions = actions + next_action\n",
    "            if min(position[0],next_position[0]) <= hole[0] <= max(position[0],next_position[0]) and \\\n",
    "               min(position[1],next_position[1]) <= hole[1] <= max(position[1],next_position[1]):\n",
    "                next_position = hole\n",
    "            next_length = length + abs(position[0]-next_position[0])+abs(position[1]-next_position[1])\n",
    "            next_min_length = min(min_length, position_length.get(next_position, 1e10))\n",
    "            if next_position not in position_length or next_length < next_min_length or \\\n",
    "               (next_length == next_min_length and next_actions < position_actions[next_position]):\n",
    "                if next_position == hole:\n",
    "                    min_length = next_length\n",
    "                if next_length in length_positions:\n",
    "                    length_positions[next_length].add(next_position)\n",
    "                else:\n",
    "                    length_positions[next_length] = {next_position}\n",
    "                    heapq.heappush(heap, next_length)\n",
    "                position_length[next_position] = next_length\n",
    "                position_actions[next_position] = next_actions\n",
    "        \n",
    "        while heap and heap[0] < min_length:\n",
    "            length = heapq.heappop(heap)\n",
    "            for position in length_positions[length]:\n",
    "                if position_length[position] < length:\n",
    "                    continue\n",
    "                actions = position_actions[position]\n",
    "                if len(actions) == 0:\n",
    "                    for next_action in ['d', 'l', 'r', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                elif actions[-1] == 'd' or actions[-1] == 'u':\n",
    "                    for next_action in ['l', 'r']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                else:\n",
    "                    for next_action in ['d', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "\n",
    "        return position_actions.get(hole, \"impossible\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        m = len(maze)\n",
    "        n = len(maze[0])\n",
    "        distance = [[float('inf') for _ in range(n)] for _ in range(m)]\n",
    "        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        position = 'rdlu'\n",
    "        path = [['impossible' for _ in range(n)] for _ in range(m)]\n",
    "        distance[ball[0]][ball[1]] = 0\n",
    "        path[ball[0]][ball[1]] = ''\n",
    "\n",
    "        queue = [ball]\n",
    "\n",
    "        while queue:\n",
    "            x, y = queue.pop(0)\n",
    "            for i, (dx, dy) in enumerate(direction):\n",
    "                newx = x + dx\n",
    "                newy = y + dy\n",
    "                length = distance[x][y]\n",
    "                s = path[x][y]\n",
    "                while 0 <= newx < m and 0 <= newy < n and maze[newx][newy] == 0 and [newx-dx, newy-dy] != hole:\n",
    "                    newx += dx\n",
    "                    newy += dy\n",
    "                    length += 1\n",
    "                \n",
    "                newx -= dx\n",
    "                newy -= dy\n",
    "                if length < distance[newx][newy] or (length == distance[newx][newy] and path[newx][newy] > s + position[i]):\n",
    "                    distance[newx][newy] = length\n",
    "                    path[newx][newy] = s + position[i]\n",
    "                    if [newx, newy] != hole:\n",
    "                        queue.append((newx, newy))\n",
    "        \n",
    "        return path[hole[0]][hole[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        directions = {'u': (-1, 0), 'd': (1, 0), 'l': (0, -1), 'r': (0, 1)}\n",
    "        \n",
    "        # Priority queue to store (distance, path, row, col)\n",
    "        pq = PriorityQueue()\n",
    "        pq.put((0, \"\", ball[0], ball[1]))\n",
    "        \n",
    "        # Visited to store the shortest distance and path for each position\n",
    "        visited = {(ball[0], ball[1]): (0, \"\")}\n",
    "        \n",
    "        while not pq.empty():\n",
    "            dist, path, row, col = pq.get()\n",
    "            \n",
    "            if (row, col) == tuple(hole):\n",
    "                return path\n",
    "            \n",
    "            for d, (dr, dc) in directions.items():\n",
    "                new_row, new_col, new_dist = row, col, dist\n",
    "                new_path = path + d\n",
    "                \n",
    "                # Roll the ball until it hits a wall or the hole\n",
    "                while 0 <= new_row + dr < m and 0 <= new_col + dc < n and maze[new_row + dr][new_col + dc] == 0:\n",
    "                    new_row += dr\n",
    "                    new_col += dc\n",
    "                    new_dist += 1\n",
    "                    \n",
    "                    # If the ball reaches the hole, stop\n",
    "                    if (new_row, new_col) == tuple(hole):\n",
    "                        break\n",
    "                \n",
    "                # If the new position is better than previous, update\n",
    "                if (new_row, new_col) not in visited or (new_dist, new_path) < visited[(new_row, new_col)]:\n",
    "                    visited[(new_row, new_col)] = (new_dist, new_path)\n",
    "                    pq.put((new_dist, new_path, new_row, new_col))\n",
    "        \n",
    "        return \"impossible\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        from queue import PriorityQueue\n",
    "\n",
    "        pq = PriorityQueue()\n",
    "\n",
    "        pq.put([0, ball, []])\n",
    "        directions = {\"r\":[0,1], \"l\":[0,-1], \"d\":[1,0], \"u\":[-1,0]}\n",
    "        visited = set()\n",
    "        ans = [float(\"inf\"), \"impossible\"]\n",
    "\n",
    "        while not pq.empty():\n",
    "            distance, node, path  = pq.get()\n",
    "            if distance > ans[0]:\n",
    "                break\n",
    "            if tuple(node) in visited:\n",
    "                continue\n",
    "            visited.add(tuple(node))\n",
    "            for direction_path, direction in directions.items():\n",
    "                di, dj = direction\n",
    "                move = 0\n",
    "                i, j = node\n",
    "                while 0<= i+di < len(maze) and 0<= j+dj< len(maze[0]) and maze[i+di][j+dj] != 1:\n",
    "                    move += 1\n",
    "                    if [i+di, j+dj] == hole:\n",
    "                        if distance+move < ans[0]:\n",
    "                            ans[0] = distance+move\n",
    "                            ans[1] = \"\".join(path+[direction_path])\n",
    "                        elif distance+move == ans[0]:\n",
    "                            ans[1] = min(ans[1], \"\".join(path+[direction_path]))\n",
    "                    i += di\n",
    "                    j += dj\n",
    "\n",
    "                if move == 0:\n",
    "                    continue\n",
    "\n",
    "                pq.put([distance+move, [i, j], path+[direction_path]])\n",
    "\n",
    "        return ans[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        # 计算矩阵型号并定义好各个方向\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        directions = [(-1, 0, 'u'), (1, 0, 'd'), (0, -1, 'l'), (0, 1, 'r')]\n",
    "        \n",
    "        # 初始化ball到各个点的距离及最优路径\n",
    "        distance = [[float('inf') for j in range(n)] for i in range(m)]\n",
    "        res = [['impossible' for j in range(n)] for i in range(m)]\n",
    "        distance[ball[0]][ball[1]] = 0\n",
    "        res[ball[0]][ball[1]] = \"\"\n",
    "        \n",
    "        # 队列中放入起始点并处理队列\n",
    "        queue = [ball]\n",
    "        while queue:\n",
    "            i, j = queue.pop()\n",
    "            for dx, dy, letter in directions:\n",
    "                # 获取当前点的距离及最优路径\n",
    "                dis, s = distance[i][j], res[i][j]\n",
    "                # 找到该方向的终点或者洞的位置\n",
    "                x, y = i + dx, j + dy\n",
    "                while 0 <= x < m and 0 <= y < n and maze[x][y] == 0 and ([x - dx, y - dy] != hole):\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "                    dis += 1\n",
    "                x = x - dx\n",
    "                y = y - dy\n",
    "                # 若该终点距离或者路径优于之前则更新，若没有到达洞的位置则将该位置加入队列\n",
    "                if dis < distance[x][y] or (dis == distance[x][y] and s + letter < res[x][y]):\n",
    "                    distance[x][y] = dis\n",
    "                    res[x][y] = s + letter\n",
    "                    if [x, y] != hole:\n",
    "                        queue.append([x, y])\n",
    "        return res[hole[0]][hole[1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        \n",
    "        ends = dict()\n",
    "        ends['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    ends['l'][i][j] = end_left+1\n",
    "        ends['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    ends['r'][i][j] = end_right-1\n",
    "        ends['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    ends['u'][i][j] = end_up+1\n",
    "        ends['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    ends['d'][i][j] = end_down-1\n",
    "        \n",
    "        heap = [0]\n",
    "        length_positions = {0:{ball}}\n",
    "        position_length = {ball:0}\n",
    "        position_actions = {ball:''}\n",
    "        global min_length\n",
    "        min_length = 1e10\n",
    "\n",
    "        def get_next_position(position, action):\n",
    "            if action == 'd' or action == 'u':\n",
    "                return (ends[action][position[0]][position[1]], position[1])\n",
    "            else:\n",
    "                return (position[0], ends[action][position[0]][position[1]])\n",
    "        \n",
    "        def one_step(position, length, actions, next_action):\n",
    "            global min_length\n",
    "            next_position = get_next_position(position, next_action)\n",
    "            next_actions = actions + next_action\n",
    "            if (min(position[0],next_position[0]) <= hole[0] <= max(position[0],next_position[0])) and \\\n",
    "               (min(position[1],next_position[1]) <= hole[1] <= max(position[1],next_position[1])):\n",
    "                next_position = hole\n",
    "                next_length = length + abs(position[0]-next_position[0])+abs(position[1]-next_position[1])\n",
    "                min_length = min(min_length, next_length)\n",
    "            else:\n",
    "                next_length = length + abs(position[0]-next_position[0])+abs(position[1]-next_position[1])\n",
    "            if next_position not in position_length or next_length < position_length[next_position] or \\\n",
    "               (next_length == position_length[next_position] and next_actions < position_actions[next_position]):\n",
    "                if next_position in position_length:\n",
    "                    length_positions[position_length[next_position]].remove(next_position)\n",
    "                if next_length in length_positions:\n",
    "                    length_positions[next_length].add(next_position)\n",
    "                else:\n",
    "                    length_positions[next_length] = {next_position}\n",
    "                    heapq.heappush(heap, next_length)\n",
    "                position_length[next_position] = next_length\n",
    "                position_actions[next_position] = next_actions\n",
    "        \n",
    "        while heap and heap[0] < min_length:\n",
    "            length = heapq.heappop(heap)\n",
    "            for position in length_positions[length]:\n",
    "                actions = position_actions[position]\n",
    "                if len(actions) == 0:\n",
    "                    for next_action in ['d', 'l', 'r', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                elif actions[-1] == 'd' or actions[-1] == 'u':\n",
    "                    for next_action in ['l', 'r']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                else:\n",
    "                    for next_action in ['d', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "\n",
    "        return position_actions.get(hole, \"impossible\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        \n",
    "        next_positions = dict()\n",
    "        next_positions['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    next_positions['l'][i][j] = end_left+1\n",
    "        next_positions['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    next_positions['r'][i][j] = end_right-1\n",
    "        next_positions['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    next_positions['u'][i][j] = end_up+1\n",
    "        next_positions['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    next_positions['d'][i][j] = end_down-1\n",
    "        \n",
    "        heap = [0]\n",
    "        length_positions = {0:{ball}}\n",
    "        position_length = {ball:0}\n",
    "        position_actions = {ball:''}\n",
    "        global min_length\n",
    "        min_length = 1e10\n",
    "\n",
    "        def get_next_position(position, action):\n",
    "            if action == 'd' or action == 'u':\n",
    "                return (next_positions[action][position[0]][position[1]], position[1])\n",
    "            else:\n",
    "                return (position[0], next_positions[action][position[0]][position[1]])\n",
    "        \n",
    "        def one_step(position, length, actions, next_action):\n",
    "            global min_length\n",
    "            next_position = get_next_position(position, next_action)\n",
    "            next_actions = actions + next_action\n",
    "            if min(position[0],next_position[0]) <= hole[0] <= max(position[0],next_position[0]) and \\\n",
    "               min(position[1],next_position[1]) <= hole[1] <= max(position[1],next_position[1]):\n",
    "                next_position = hole\n",
    "            next_length = length + abs(position[0]-next_position[0])+abs(position[1]-next_position[1])\n",
    "            if next_position not in position_length or next_length < position_length[next_position] or \\\n",
    "               (next_length == position_length[next_position] and next_actions < position_actions[next_position]):\n",
    "                if next_position == hole:\n",
    "                    min_length = next_length\n",
    "                # if next_position in position_length:\n",
    "                #     length_positions[position_length[next_position]].remove(next_position)\n",
    "                if next_length in length_positions:\n",
    "                    length_positions[next_length].add(next_position)\n",
    "                else:\n",
    "                    length_positions[next_length] = {next_position}\n",
    "                    heapq.heappush(heap, next_length)\n",
    "                position_length[next_position] = next_length\n",
    "                position_actions[next_position] = next_actions\n",
    "        \n",
    "        while heap and heap[0] < min_length:\n",
    "            length = heapq.heappop(heap)\n",
    "            for position in length_positions[length]:\n",
    "                if position_length[position] < length:\n",
    "                    continue\n",
    "                actions = position_actions[position]\n",
    "                if len(actions) == 0:\n",
    "                    for next_action in ['d', 'l', 'r', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                elif actions[-1] == 'd' or actions[-1] == 'u':\n",
    "                    for next_action in ['l', 'r']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                else:\n",
    "                    for next_action in ['d', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "\n",
    "        return position_actions.get(hole, \"impossible\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        \n",
    "        next_positions = dict()\n",
    "        next_positions['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    next_positions['l'][i][j] = end_left+1\n",
    "        next_positions['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    next_positions['r'][i][j] = end_right-1\n",
    "        next_positions['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    next_positions['u'][i][j] = end_up+1\n",
    "        next_positions['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    next_positions['d'][i][j] = end_down-1\n",
    "        \n",
    "        heap = [0]\n",
    "        length_positions = {0:{ball}}\n",
    "        position_length = {ball:0}\n",
    "        position_actions = {ball:''}\n",
    "        global min_length\n",
    "        min_length = 1e10\n",
    "\n",
    "        def get_next_position(position, action):\n",
    "            if action == 'd' or action == 'u':\n",
    "                return (next_positions[action][position[0]][position[1]], position[1])\n",
    "            else:\n",
    "                return (position[0], next_positions[action][position[0]][position[1]])\n",
    "        \n",
    "        def one_step(position, length, actions, next_action):\n",
    "            global min_length\n",
    "            next_position = get_next_position(position, next_action)\n",
    "            next_actions = actions + next_action\n",
    "            if min(position[0],next_position[0]) <= hole[0] <= max(position[0],next_position[0]) and \\\n",
    "               min(position[1],next_position[1]) <= hole[1] <= max(position[1],next_position[1]):\n",
    "                next_position = hole\n",
    "            next_length = length + abs(position[0]-next_position[0])+abs(position[1]-next_position[1])\n",
    "            if next_position in position_length:\n",
    "                next_min_length = min(min_length, position_length[next_position])\n",
    "            if next_position not in position_length or next_length < next_min_length or \\\n",
    "               (next_length == next_min_length and next_actions < position_actions[next_position]):\n",
    "                if next_position == hole:\n",
    "                    min_length = next_length\n",
    "                if next_position in position_length:\n",
    "                    length_positions[position_length[next_position]].remove(next_position)\n",
    "                if next_length in length_positions:\n",
    "                    length_positions[next_length].add(next_position)\n",
    "                else:\n",
    "                    length_positions[next_length] = {next_position}\n",
    "                    heapq.heappush(heap, next_length)\n",
    "                position_length[next_position] = next_length\n",
    "                position_actions[next_position] = next_actions\n",
    "        \n",
    "        while heap and heap[0] < min_length:\n",
    "            length = heapq.heappop(heap)\n",
    "            for position in length_positions[length]:\n",
    "                # if position_length[position] < length:\n",
    "                #     continue\n",
    "                actions = position_actions[position]\n",
    "                if len(actions) == 0:\n",
    "                    for next_action in ['d', 'l', 'r', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                elif actions[-1] == 'd' or actions[-1] == 'u':\n",
    "                    for next_action in ['l', 'r']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                else:\n",
    "                    for next_action in ['d', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "\n",
    "        return position_actions.get(hole, \"impossible\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        stack = [[0, ball[0], ball[1], '', 's']]\n",
    "        visit = set()\n",
    "        direc = {'l': [0, -1], 'r': [0, 1], 'u': [-1, 0], 'd': [1, 0]}\n",
    "        g = [[inf] * n for _ in range(m)]\n",
    "        g[ball[0]][ball[1]] = 0\n",
    "        shortest = float('inf')\n",
    "        ans = \"\"\n",
    "        while stack:\n",
    "            dis, i, j, path, state = heapq.heappop(stack)\n",
    "\n",
    "            # # 访问过或者距离超出\n",
    "            # if (i, j, state) in visit or dis > shortest:\n",
    "            #     continue\n",
    "            # visit.add((i, j, state))\n",
    "\n",
    "            # # 到达终点\n",
    "            # if [i, j] == hole:\n",
    "            #     shortest = dis\n",
    "            #     if not ans or ans > path:\n",
    "            #         ans = path\n",
    "            #     continue\n",
    "\n",
    "            if (state, i, j) in visit or dis > shortest:\n",
    "                continue\n",
    "            visit.add((state, i, j))\n",
    "\n",
    "            # 到达终点\n",
    "            if [i, j] == hole:\n",
    "                shortest = dis\n",
    "                if not ans or ans > path:\n",
    "                    ans = path\n",
    "                continue\n",
    "\n",
    "            # 进入固定态换方向\n",
    "            if state == 's':\n",
    "                for d in direc:\n",
    "                    heapq.heappush(stack, [dis, i, j, path+d, d])\n",
    "                continue\n",
    "\n",
    "            # 继续前行或者进入固定态\n",
    "            x, y = i + direc[state][0], j + direc[state][1]\n",
    "            if not (0 <= x < m and 0 <= y < n) or maze[x][y] == 1:\n",
    "                heapq.heappush(stack, [dis, i, j, path, 's'])\n",
    "            else:\n",
    "                heapq.heappush(stack, [dis + 1, x, y, path, state])\n",
    "        return ans if ans else \"impossible\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        from collections import deque\n",
    "        directions = [(0, 1, \"r\"), (0, -1, \"l\"), (1, 0, \"d\"), (-1, 0, \"u\")]\n",
    "\n",
    "\n",
    "        dis_map = dict()\n",
    "        queue = deque()\n",
    "        dis_q = deque()\n",
    "\n",
    "        queue.append(tuple(ball))\n",
    "        dis_q.append((0, \"\"))\n",
    "        dis_map[tuple(ball)] = 0\n",
    "        dest_pos = tuple(hole)\n",
    "        \n",
    "        def next_positions(cur_position):\n",
    "            res = []\n",
    "            for d_x, d_y, d in directions:\n",
    "                new_x, new_y = cur_position\n",
    "                dis = 0\n",
    "                while (\n",
    "                    0 <= new_x < len(maze) and 0<= new_y < len(maze[0]) \n",
    "                    and maze[new_x][new_y] != 1\n",
    "                    and (new_x, new_y) != dest_pos\n",
    "                ):\n",
    "                    new_x, new_y = new_x + d_x, new_y + d_y\n",
    "                    dis += 1\n",
    "                \n",
    "                # reset to last step\n",
    "                if (new_x, new_y) != dest_pos:\n",
    "                    new_x, new_y = new_x - d_x, new_y - d_y\n",
    "                    dis -= 1\n",
    "                \n",
    "                if (new_x, new_y) != cur_position:\n",
    "                    res.append((new_x, new_y, dis, d))\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        distances = []\n",
    "        while queue:\n",
    "            cur_pos = queue.popleft()\n",
    "            cur_distance, cur_path_str = dis_q.popleft() # distance so far\n",
    "            \n",
    "            if cur_pos == dest_pos:\n",
    "                distances.append((cur_distance, cur_path_str))\n",
    "                continue\n",
    "\n",
    "            for x, y, dis, d in next_positions(cur_pos):\n",
    "                if (x, y) not in dis_map or cur_distance + dis <= dis_map[(x, y)]:\n",
    "                    dis_map[(x, y)] = cur_distance + dis\n",
    "                    queue.append((x, y))\n",
    "                    dis_q.append((cur_distance + dis, cur_path_str + d))\n",
    "        \n",
    "        distances.sort(key=lambda k: (k[0], k[1]))\n",
    "        # print(distances)\n",
    "        \n",
    "        return distances[0][1] if distances else \"impossible\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int])->str:\n",
    "        INF=0x3f3f3f3f\n",
    "        self.dr=[1,0,0,-1]                \t\t#垂直方向偏移量\n",
    "        self.dc=[0,-1,1,0]                 \t\t#水平方向偏移量\n",
    "        self.dirstr=[\"d\",\"l\",\"r\",\"u\"]           #方位：字典序最小\n",
    "        self.m,self.n=len(maze),len(maze[0])\n",
    "        self.dist=[[INF for _ in range(self.n)] for _ in range(self.m)]\n",
    "        self.path=[[\"\" for _ in range(self.n)] for _ in range(self.m)]\n",
    "        sr,sc=ball[0],ball[1]\n",
    "        self.hr,self.hc=hole[0],hole[1]\n",
    "        self.dist[sr][sc]=0\n",
    "        self.dfs(maze,sr,sc)\n",
    "        ans=self.path[self.hr][self.hc]\n",
    "        return \"impossible\" if ans==\"\" else ans\n",
    "    def dfs(self,maze,r,c):\n",
    "        for di in range(0,4):\n",
    "            delta=0\n",
    "            nr,nc=r,c\n",
    "            while nr+self.dr[di]>=0 and nr+self.dr[di]<self.m  \\\n",
    "                    and nc+self.dc[di]>=0 and nc+self.dc[di]<self.n and \\\n",
    "                    maze[nr+self.dr[di]][nc+self.dc[di]]==0: \n",
    "                nr+=self.dr[di]\n",
    "                nc+=self.dc[di]\n",
    "                delta+=1\n",
    "                if nr==self.hr and nc==self.hc:   #(nr,nc)为洞\n",
    "                    break;\n",
    "            curdist=self.dist[r][c]+delta\n",
    "            curpath=self.path[r][c]+self.dirstr[di]\n",
    "            if curdist<self.dist[nr][nc]:\t\t\t#边松驰\n",
    "                self.dist[nr][nc]=curdist\n",
    "                self.path[nr][nc]=curpath\n",
    "                if nr!=self.hr or nc!=self.hc:       #(nr,nc)不是洞\n",
    "                    self.dfs(maze,nr,nc)\n",
    "            elif curdist==self.dist[nr][nc]:\n",
    "                if curpath<self.path[nr][nc]:     #找最小序路径\n",
    "                    self.path[nr][nc]=curpath;\n",
    "                    if nr!=self.hr or nc!=self.hc:    #(nr,nc)不是洞\n",
    "                        self.dfs(maze,nr,nc)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        M = len(maze)\n",
    "        N = len(maze[0])\n",
    "        Q = deque([])\n",
    "        dp = [ [ [float(\"inf\"),\"\"] for _ in range(N) ] for _ in range(M) ]\n",
    "        # d -- 0上 1下 2左 3右\n",
    "        dx = [ -1, 1, 0, 0 ]\n",
    "        dy = [ 0, 0, -1, 1 ]\n",
    "        dic = { 0:\"u\", 1:\"d\", 2:\"l\", 3:\"r\" }\n",
    "        def run():\n",
    "            while Q:\n",
    "                x, y = Q.popleft()\n",
    "                for d in range(4):\n",
    "                    tx, ty = x, y\n",
    "                    ex, ey = x + dx[d], y + dy[d]\n",
    "                    step = 0\n",
    "                    while ex >= 0 and ex < M and ey >= 0 and ey < N and maze[ex][ey] == 0:\n",
    "                        tx, ty = ex, ey\n",
    "                        ex += dx[d]\n",
    "                        ey += dy[d]\n",
    "                        step += 1\n",
    "                        if tx == hole[0] and ty == hole[1]:\n",
    "                            break\n",
    "                    if dp[x][y][0] + step < dp[tx][ty][0]:\n",
    "                        dp[tx][ty] = [dp[x][y][0] + step, dp[x][y][1] + dic[d]]\n",
    "                        Q.append((tx, ty))\n",
    "                    elif dp[x][y][0] + step == dp[tx][ty][0] and dp[x][y][1] < dp[tx][ty][1]:\n",
    "                        dp[tx][ty] = [dp[tx][ty][0], dp[x][y][1] + dic[d]]\n",
    "                        Q.append((tx, ty))\n",
    "        Q.append((ball[0], ball[1]))\n",
    "        dp[ball[0]][ball[1]] = [0, \"\"]\n",
    "        run()\n",
    "        print(dp)\n",
    "        return \"impossible\" if dp[hole[0]][hole[1]][0] == float(\"inf\") else dp[hole[0]][hole[1]][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        \n",
    "        ends = dict()\n",
    "        ends['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    ends['l'][i][j] = end_left+1\n",
    "        ends['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    ends['r'][i][j] = end_right-1\n",
    "        ends['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    ends['u'][i][j] = end_up+1\n",
    "        ends['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    ends['d'][i][j] = end_down-1\n",
    "        \n",
    "        heap = [0]\n",
    "        length_positions = {0:{ball}}\n",
    "        position_length = {ball:0}\n",
    "        position_actions = {ball:''}\n",
    "        global min_length\n",
    "        min_length = 1e10\n",
    "\n",
    "        def get_next_position(position, action):\n",
    "            if action == 'd' or action == 'u':\n",
    "                return (ends[action][position[0]][position[1]], position[1])\n",
    "            else:\n",
    "                return (position[0], ends[action][position[0]][position[1]])\n",
    "        \n",
    "        def one_step(position, length, actions, next_action):\n",
    "            global min_length\n",
    "            next_position = get_next_position(position, next_action)\n",
    "            next_actions = actions + next_action\n",
    "            if min(position[0],next_position[0]) <= hole[0] <= max(position[0],next_position[0]) and \\\n",
    "               min(position[1],next_position[1]) <= hole[1] <= max(position[1],next_position[1]):\n",
    "                next_position = hole\n",
    "                next_length = length + abs(position[0]-next_position[0])+abs(position[1]-next_position[1])\n",
    "                min_length = min(min_length, next_length)\n",
    "            else:\n",
    "                next_length = length + abs(position[0]-next_position[0])+abs(position[1]-next_position[1])\n",
    "            if next_position not in position_length or next_length < position_length[next_position] or \\\n",
    "               (next_length == position_length[next_position] and next_actions < position_actions[next_position]):\n",
    "                if next_position in position_length:\n",
    "                    length_positions[position_length[next_position]].remove(next_position)\n",
    "                if next_length in length_positions:\n",
    "                    length_positions[next_length].add(next_position)\n",
    "                else:\n",
    "                    length_positions[next_length] = {next_position}\n",
    "                    heapq.heappush(heap, next_length)\n",
    "                position_length[next_position] = next_length\n",
    "                position_actions[next_position] = next_actions\n",
    "        \n",
    "        while heap and heap[0] < min_length:\n",
    "            length = heapq.heappop(heap)\n",
    "            for position in length_positions[length]:\n",
    "                actions = position_actions[position]\n",
    "                if len(actions) == 0:\n",
    "                    for next_action in ['d', 'l', 'r', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                elif actions[-1] == 'd' or actions[-1] == 'u':\n",
    "                    for next_action in ['l', 'r']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                else:\n",
    "                    for next_action in ['d', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "\n",
    "        return position_actions.get(hole, \"impossible\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        def check(x, y):\n",
    "            return 0 <= x < m and 0 <= y < n and not maze[x][y]\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        # 初始化搜索状态\n",
    "        ind = {\"d\": [1, 0], \"u\": [-1, 0], \"l\": [0, -1], \"r\": [0, 1]}\n",
    "        ans = \"z\"\n",
    "        stack = [[ball[0], ball[1], d] for d in ind if check(ball[0] + ind[d][0], ball[1] + ind[d][1])]\n",
    "        visit = defaultdict(set)\n",
    "        while stack and ans == \"z\":\n",
    "            nex = []\n",
    "            # 在每轮搜索前使用坐标加方向先把历史状态进行记录\n",
    "            for x, y, path in stack:\n",
    "                # 同样的点同样的方向不应该有距离更长的搜索但有可能距离相同但路径不一样\n",
    "                visit[(x, y)].add(path[-1])\n",
    "            for x, y, path in stack:\n",
    "                if [x, y] == hole:\n",
    "                    ans = min(ans, path)\n",
    "                    continue\n",
    "                # 继续前进\n",
    "                a, b = x + ind[path[-1]][0], y + ind[path[-1]][1]\n",
    "                if check(a, b):\n",
    "                    if path[-1] not in visit[(a, b)]:\n",
    "                        nex.append([a, b, path])\n",
    "                else:\n",
    "                    # 换方向前进\n",
    "                    for d in ind:\n",
    "                        if d != path[-1]:\n",
    "                            a, b = x + ind[d][0], y + ind[d][1]\n",
    "                            if check(a, b) and d not in visit[(a, b)]:\n",
    "                                nex.append([a, b, path + d])\n",
    "            stack = nex\n",
    "        return ans if ans != \"z\" else \"impossible\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        \n",
    "        next_positions = dict()\n",
    "        next_positions['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    next_positions['l'][i][j] = end_left+1\n",
    "        next_positions['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    next_positions['r'][i][j] = end_right-1\n",
    "        next_positions['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    next_positions['u'][i][j] = end_up+1\n",
    "        next_positions['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    next_positions['d'][i][j] = end_down-1\n",
    "        \n",
    "        heap = [0]\n",
    "        length_positions = {0:{ball}}\n",
    "        position_length = {ball:0}\n",
    "        position_actions = {ball:''}\n",
    "        global min_length\n",
    "        min_length = 1e10\n",
    "\n",
    "        def get_next_position(position, action):\n",
    "            if action == 'd' or action == 'u':\n",
    "                return (next_positions[action][position[0]][position[1]], position[1])\n",
    "            else:\n",
    "                return (position[0], next_positions[action][position[0]][position[1]])\n",
    "        \n",
    "        def one_step(position, length, actions, next_action):\n",
    "            global min_length\n",
    "            next_position = get_next_position(position, next_action)\n",
    "            next_actions = actions + next_action\n",
    "            if min(position[0],next_position[0]) <= hole[0] <= max(position[0],next_position[0]) and \\\n",
    "               min(position[1],next_position[1]) <= hole[1] <= max(position[1],next_position[1]):\n",
    "                next_position = hole\n",
    "            next_length = length + abs(position[0]-next_position[0])+abs(position[1]-next_position[1])\n",
    "            next_min_length = min(min_length, position_length.get(next_position, 1e10))\n",
    "            if next_position not in position_length or next_length < next_min_length or \\\n",
    "               (next_length == next_min_length and next_actions < position_actions[next_position]):\n",
    "                if next_position == hole:\n",
    "                    min_length = next_length\n",
    "                if next_length in length_positions:\n",
    "                    length_positions[next_length].add(next_position)\n",
    "                else:\n",
    "                    length_positions[next_length] = {next_position}\n",
    "                    heapq.heappush(heap, next_length)\n",
    "                position_length[next_position] = next_length\n",
    "                position_actions[next_position] = next_actions\n",
    "        \n",
    "        while heap and heap[0] < min_length:\n",
    "            length = heapq.heappop(heap)\n",
    "            for position in length_positions[length]:\n",
    "                if position_length[position] < length:\n",
    "                    continue\n",
    "                actions = position_actions[position]\n",
    "                if len(actions) == 0:\n",
    "                    for next_action in ['d', 'l', 'r', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                elif actions[-1] == 'd' or actions[-1] == 'u':\n",
    "                    for next_action in ['l', 'r']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                else:\n",
    "                    for next_action in ['d', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "\n",
    "        return position_actions.get(hole, \"impossible\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        \n",
    "        next_positions = dict()\n",
    "        next_positions['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    next_positions['l'][i][j] = end_left+1\n",
    "        next_positions['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    next_positions['r'][i][j] = end_right-1\n",
    "        next_positions['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    next_positions['u'][i][j] = end_up+1\n",
    "        next_positions['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    next_positions['d'][i][j] = end_down-1\n",
    "        \n",
    "        heap = [0]\n",
    "        length_positions = {0:{ball}}\n",
    "        position_length = {ball:0}\n",
    "        position_actions = {ball:''}\n",
    "        global min_length\n",
    "        min_length = 1e10\n",
    "\n",
    "        def get_next_position(position, action):\n",
    "            if action == 'd' or action == 'u':\n",
    "                return (next_positions[action][position[0]][position[1]], position[1])\n",
    "            else:\n",
    "                return (position[0], next_positions[action][position[0]][position[1]])\n",
    "        \n",
    "        def one_step(position, length, actions, next_action):\n",
    "            global min_length\n",
    "            next_position = get_next_position(position, next_action)\n",
    "            next_actions = actions + next_action\n",
    "            if min(position[0],next_position[0]) <= hole[0] <= max(position[0],next_position[0]) and \\\n",
    "               min(position[1],next_position[1]) <= hole[1] <= max(position[1],next_position[1]):\n",
    "                next_position = hole\n",
    "            next_length = length + abs(position[0]-next_position[0])+abs(position[1]-next_position[1])\n",
    "            if next_position not in position_length or next_length < position_length[next_position] or \\\n",
    "               (next_length == position_length[next_position] and next_actions < position_actions[next_position]):\n",
    "                if next_position == hole:\n",
    "                    min_length = next_length\n",
    "                # if next_position in position_length:\n",
    "                #     length_positions[position_length[next_position]].remove(next_position)\n",
    "                if next_length in length_positions:\n",
    "                    length_positions[next_length].add(next_position)\n",
    "                else:\n",
    "                    length_positions[next_length] = {next_position}\n",
    "                    heapq.heappush(heap, next_length)\n",
    "                position_length[next_position] = next_length\n",
    "                position_actions[next_position] = next_actions\n",
    "        \n",
    "        while heap and heap[0] < min_length:\n",
    "            length = heapq.heappop(heap)\n",
    "            for position in length_positions[length]:\n",
    "                if position_length[position] < length:\n",
    "                    continue\n",
    "                actions = position_actions[position]\n",
    "                if len(actions) == 0:\n",
    "                    for next_action in ['d', 'l', 'r', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                elif actions[-1] == 'd' or actions[-1] == 'u':\n",
    "                    for next_action in ['l', 'r']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                else:\n",
    "                    for next_action in ['d', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "\n",
    "        return position_actions.get(hole, \"impossible\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        ends = dict()\n",
    "        ends['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    ends['l'][i][j] = end_left+1\n",
    "        ends['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    ends['r'][i][j] = end_right-1\n",
    "        ends['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    ends['u'][i][j] = end_up+1\n",
    "        ends['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    ends['d'][i][j] = end_down-1\n",
    "        \n",
    "        global min_length\n",
    "        global min_res\n",
    "        min_length = 1e10\n",
    "        min_res = None\n",
    "        def update_res(length, res):\n",
    "            global min_length\n",
    "            global min_res\n",
    "            if length < min_length:\n",
    "                min_length = length\n",
    "                min_res = res\n",
    "            elif length == min_length and res < min_res:\n",
    "                min_res = res\n",
    "\n",
    "        def recursion(ball, action, path, length, res):\n",
    "            if action == 'd' or action == 'u':\n",
    "                ball_next = (ends[action][ball[0]][ball[1]], ball[1])\n",
    "                if path.get(ball_next,1e10) <= length+abs(ball[0]-ball_next[0]):\n",
    "                    return\n",
    "                res += action\n",
    "                if hole[1] == ball[1] and min(ball[0],ball_next[0]) <= hole[0] <= max(ball[0],ball_next[0]):\n",
    "                    length += abs(ball[0]-hole[0])\n",
    "                    update_res(length, res)\n",
    "                    return\n",
    "                length += abs(ball[0]-ball_next[0])\n",
    "                path[ball_next] = length\n",
    "                for action_next in ['l', 'r']:\n",
    "                    ans = recursion(ball_next, action_next, path, length, res[:])\n",
    "            else:\n",
    "                ball_next = (ball[0], ends[action][ball[0]][ball[1]])\n",
    "                if path.get(ball_next,1e10) <= length+abs(ball[1]-ball_next[1]):\n",
    "                    return\n",
    "                res += action\n",
    "                if hole[0] == ball[0] and min(ball[1],ball_next[1]) <= hole[1] <= max(ball[1],ball_next[1]):\n",
    "                    length += abs(ball[1]-hole[1])\n",
    "                    update_res(length, res)\n",
    "                    return\n",
    "                length += abs(ball[1]-ball_next[1])\n",
    "                path[ball_next] = length\n",
    "                for action_next in ['d', 'u']:\n",
    "                    ans = recursion(ball_next, action_next, path, length, res[:])\n",
    "        for action in ['d', 'l', 'r', 'u']:\n",
    "            recursion(ball, action, {ball:0}, 0, '')\n",
    "        if min_res is None:\n",
    "            return \"impossible\"\n",
    "        return min_res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        \n",
    "        next_positions = dict()\n",
    "        next_positions['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    next_positions['l'][i][j] = end_left+1\n",
    "        next_positions['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    next_positions['r'][i][j] = end_right-1\n",
    "        next_positions['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    next_positions['u'][i][j] = end_up+1\n",
    "        next_positions['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    next_positions['d'][i][j] = end_down-1\n",
    "        \n",
    "        heap = [0]\n",
    "        length_positions = {0:{ball}}\n",
    "        position_length = {ball:0}\n",
    "        position_actions = {ball:''}\n",
    "        global min_length\n",
    "        min_length = 1e10\n",
    "\n",
    "        def get_next_position(position, action):\n",
    "            if action == 'd' or action == 'u':\n",
    "                return (next_positions[action][position[0]][position[1]], position[1])\n",
    "            else:\n",
    "                return (position[0], next_positions[action][position[0]][position[1]])\n",
    "        \n",
    "        def one_step(position, length, actions, next_action):\n",
    "            global min_length\n",
    "            next_position = get_next_position(position, next_action)\n",
    "            next_actions = actions + next_action\n",
    "            if min(position[0],next_position[0]) <= hole[0] <= max(position[0],next_position[0]) and \\\n",
    "               min(position[1],next_position[1]) <= hole[1] <= max(position[1],next_position[1]):\n",
    "                next_position = hole\n",
    "            next_length = length + abs(position[0]-next_position[0])+abs(position[1]-next_position[1])\n",
    "            if next_position not in position_length or next_length < position_length[next_position] or \\\n",
    "               (next_length == position_length[next_position] and next_actions < position_actions[next_position]):\n",
    "                if next_position == hole:\n",
    "                    min_length = next_length\n",
    "                if next_position in position_length:\n",
    "                    length_positions[position_length[next_position]].remove(next_position)\n",
    "                if next_length in length_positions:\n",
    "                    length_positions[next_length].add(next_position)\n",
    "                else:\n",
    "                    length_positions[next_length] = {next_position}\n",
    "                    heapq.heappush(heap, next_length)\n",
    "                position_length[next_position] = next_length\n",
    "                position_actions[next_position] = next_actions\n",
    "        \n",
    "        while heap and heap[0] < min_length:\n",
    "            length = heapq.heappop(heap)\n",
    "            for position in length_positions[length]:\n",
    "                actions = position_actions[position]\n",
    "                if len(actions) == 0:\n",
    "                    for next_action in ['d', 'l', 'r', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                elif actions[-1] == 'd' or actions[-1] == 'u':\n",
    "                    for next_action in ['l', 'r']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                else:\n",
    "                    for next_action in ['d', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "\n",
    "        return position_actions.get(hole, \"impossible\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        \n",
    "        next_positions = dict()\n",
    "        next_positions['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    next_positions['l'][i][j] = end_left+1\n",
    "        next_positions['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    next_positions['r'][i][j] = end_right-1\n",
    "        next_positions['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    next_positions['u'][i][j] = end_up+1\n",
    "        next_positions['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    next_positions['d'][i][j] = end_down-1\n",
    "        \n",
    "        heap = [0]\n",
    "        length_positions = {0:{ball}}\n",
    "        position_length = {ball:0}\n",
    "        position_actions = {ball:''}\n",
    "        global min_length\n",
    "        min_length = 1e10\n",
    "\n",
    "        def get_next_position(position, action):\n",
    "            if action == 'd' or action == 'u':\n",
    "                return (next_positions[action][position[0]][position[1]], position[1])\n",
    "            else:\n",
    "                return (position[0], next_positions[action][position[0]][position[1]])\n",
    "        \n",
    "        def one_step(position, length, actions, next_action):\n",
    "            global min_length\n",
    "            next_position = get_next_position(position, next_action)\n",
    "            next_actions = actions + next_action\n",
    "            if min(position[0],next_position[0]) <= hole[0] <= max(position[0],next_position[0]) and \\\n",
    "               min(position[1],next_position[1]) <= hole[1] <= max(position[1],next_position[1]):\n",
    "                next_position = hole\n",
    "            next_length = length + abs(position[0]-next_position[0])+abs(position[1]-next_position[1])\n",
    "            if next_position not in position_length or next_length < position_length[next_position] or \\\n",
    "               (next_length == position_length[next_position] and next_actions < position_actions[next_position]):\n",
    "                if next_position == hole:\n",
    "                    min_length = next_length\n",
    "                if next_position in position_length:\n",
    "                    length_positions[position_length[next_position]].remove(next_position)\n",
    "                if next_length in length_positions:\n",
    "                    length_positions[next_length].add(next_position)\n",
    "                else:\n",
    "                    length_positions[next_length] = {next_position}\n",
    "                    heapq.heappush(heap, next_length)\n",
    "                position_length[next_position] = next_length\n",
    "                position_actions[next_position] = next_actions\n",
    "        \n",
    "        while heap and heap[0] < min_length:\n",
    "            length = heapq.heappop(heap)\n",
    "            for position in length_positions[length]:\n",
    "                # if position_length[position] < length:\n",
    "                #     continue\n",
    "                actions = position_actions[position]\n",
    "                if len(actions) == 0:\n",
    "                    for next_action in ['d', 'l', 'r', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                elif actions[-1] == 'd' or actions[-1] == 'u':\n",
    "                    for next_action in ['l', 'r']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "                else:\n",
    "                    for next_action in ['d', 'u']:\n",
    "                        one_step(position, length, actions, next_action)\n",
    "\n",
    "        return position_actions.get(hole, \"impossible\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        ends = dict()\n",
    "        ends['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    ends['l'][i][j] = end_left+1\n",
    "        ends['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    ends['r'][i][j] = end_right-1\n",
    "        ends['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    ends['u'][i][j] = end_up+1\n",
    "        ends['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    ends['d'][i][j] = end_down-1\n",
    "        \n",
    "        global min_length\n",
    "        global min_res\n",
    "        min_length = 1e10\n",
    "        min_res = None\n",
    "        def update_res(length, res):\n",
    "            global min_length\n",
    "            global min_res\n",
    "            if length < min_length:\n",
    "                min_length = length\n",
    "                min_res = res\n",
    "            elif length == min_length and res < min_res:\n",
    "                min_res = res\n",
    "\n",
    "        def recursion(ball, action, path, length, res):\n",
    "            if action == 'd' or action == 'u':\n",
    "                ball_next = (ends[action][ball[0]][ball[1]], ball[1])\n",
    "                if path.get(ball_next,1e10) <= length+abs(ball[0]-ball_next[0]):\n",
    "                    return\n",
    "                res += action\n",
    "                if hole[1] == ball[1] and min(ball[0],ball_next[0]) <= hole[0] <= max(ball[0],ball_next[0]):\n",
    "                    length += abs(ball[0]-hole[0])\n",
    "                    update_res(length, res)\n",
    "                    return\n",
    "                length += abs(ball[0]-ball_next[0])\n",
    "                path[ball_next] = length\n",
    "                if length >= min_length:\n",
    "                    return\n",
    "                for action_next in ['l', 'r']:\n",
    "                    ans = recursion(ball_next, action_next, path, length, res[:])\n",
    "            else:\n",
    "                ball_next = (ball[0], ends[action][ball[0]][ball[1]])\n",
    "                if path.get(ball_next,1e10) <= length+abs(ball[1]-ball_next[1]):\n",
    "                    return\n",
    "                res += action\n",
    "                if hole[0] == ball[0] and min(ball[1],ball_next[1]) <= hole[1] <= max(ball[1],ball_next[1]):\n",
    "                    length += abs(ball[1]-hole[1])\n",
    "                    update_res(length, res)\n",
    "                    return\n",
    "                length += abs(ball[1]-ball_next[1])\n",
    "                path[ball_next] = length\n",
    "                if length >= min_length:\n",
    "                    return\n",
    "                for action_next in ['d', 'u']:\n",
    "                    ans = recursion(ball_next, action_next, path, length, res[:])\n",
    "        for action in ['d', 'l', 'r', 'u']:\n",
    "            recursion(ball, action, {ball:0}, 0, '')\n",
    "        if min_res is None:\n",
    "            return \"impossible\"\n",
    "        return min_res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        ends = dict()\n",
    "        ends['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    ends['l'][i][j] = end_left+1\n",
    "        ends['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    ends['r'][i][j] = end_right-1\n",
    "        ends['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    ends['u'][i][j] = end_up+1\n",
    "        ends['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    ends['d'][i][j] = end_down-1\n",
    "        \n",
    "        global min_length\n",
    "        global min_res\n",
    "        min_length = 1e10\n",
    "        min_res = None\n",
    "        def update_res(length, res):\n",
    "            global min_length\n",
    "            global min_res\n",
    "            if length < min_length:\n",
    "                min_length = length\n",
    "                min_res = res\n",
    "            elif length == min_length and res < min_res:\n",
    "                min_res = res\n",
    "\n",
    "        def recursion(ball, action, path, length, res):\n",
    "            if action == 'd' or action == 'u':\n",
    "                ball_next = (ends[action][ball[0]][ball[1]], ball[1])\n",
    "                if path.get(ball_next,1e10) <= length+abs(ball[0]-ball_next[0]):\n",
    "                    return\n",
    "                res += action\n",
    "                if hole[1] == ball[1] and min(ball[0],ball_next[0]) <= hole[0] <= max(ball[0],ball_next[0]):\n",
    "                    length += abs(ball[0]-hole[0])\n",
    "                    update_res(length, res)\n",
    "                    return\n",
    "                length += abs(ball[0]-ball_next[0])\n",
    "                path[ball_next] = length\n",
    "                if length >= min_length:\n",
    "                    return\n",
    "                for action_next in ['l', 'r']:\n",
    "                    ans = recursion(ball_next, action_next, path, length, res[:])\n",
    "            else:\n",
    "                ball_next = (ball[0], ends[action][ball[0]][ball[1]])\n",
    "                if path.get(ball_next,1e10) <= length+abs(ball[1]-ball_next[1]):\n",
    "                    return\n",
    "                res += action\n",
    "                if hole[0] == ball[0] and min(ball[1],ball_next[1]) <= hole[1] <= max(ball[1],ball_next[1]):\n",
    "                    length += abs(ball[1]-hole[1])\n",
    "                    update_res(length, res)\n",
    "                    return\n",
    "                length += abs(ball[1]-ball_next[1])\n",
    "                path[ball_next] = length\n",
    "                if length >= min_length:\n",
    "                    return\n",
    "                for action_next in ['d', 'u']:\n",
    "                    ans = recursion(ball_next, action_next, path, length, res[:])\n",
    "        for action in ['d', 'l', 'r', 'u']:\n",
    "            recursion(ball, action, {ball:0}, 0, '')\n",
    "        if min_res is None:\n",
    "            return \"impossible\"\n",
    "        return min_res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        \n",
    "        ends = dict()\n",
    "        ends['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    ends['l'][i][j] = end_left+1\n",
    "        ends['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    ends['r'][i][j] = end_right-1\n",
    "        ends['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    ends['u'][i][j] = end_up+1\n",
    "        ends['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    ends['d'][i][j] = end_down-1\n",
    "        \n",
    "        global min_length\n",
    "        global min_res\n",
    "        min_length = 1e10\n",
    "        min_res = None\n",
    "        def update_res(length, res):\n",
    "            global min_length\n",
    "            global min_res\n",
    "            if length < min_length:\n",
    "                min_length = length\n",
    "                min_res = res\n",
    "            elif length == min_length and res < min_res:\n",
    "                min_res = res\n",
    "\n",
    "        def recursion(ball, action, path, length, res):\n",
    "            if action == 'd' or action == 'u':\n",
    "                ball_next = (ends[action][ball[0]][ball[1]], ball[1])\n",
    "                if path.get(ball_next,1e10) <= length+abs(ball[0]-ball_next[0]):\n",
    "                    return\n",
    "                res += action\n",
    "                if hole[1] == ball[1] and min(ball[0],ball_next[0]) <= hole[0] <= max(ball[0],ball_next[0]):\n",
    "                    length += abs(ball[0]-hole[0])\n",
    "                    update_res(length, res)\n",
    "                    return\n",
    "                length += abs(ball[0]-ball_next[0])\n",
    "                path[ball_next] = length\n",
    "                for action_next in ['l', 'r']:\n",
    "                    ans = recursion(ball_next, action_next, path, length, res[:])\n",
    "            else:\n",
    "                ball_next = (ball[0], ends[action][ball[0]][ball[1]])\n",
    "                if path.get(ball_next,1e10) <= length+abs(ball[1]-ball_next[1]):\n",
    "                    return\n",
    "                res += action\n",
    "                if hole[0] == ball[0] and min(ball[1],ball_next[1]) <= hole[1] <= max(ball[1],ball_next[1]):\n",
    "                    length += abs(ball[1]-hole[1])\n",
    "                    update_res(length, res)\n",
    "                    return\n",
    "                length += abs(ball[1]-ball_next[1])\n",
    "                path[ball_next] = length\n",
    "                for action_next in ['d', 'u']:\n",
    "                    ans = recursion(ball_next, action_next, path, length, res[:])\n",
    "        for action in ['d', 'l', 'r', 'u']:\n",
    "            recursion(ball, action, {ball:0}, 0, '')\n",
    "        if min_res is None:\n",
    "            return \"impossible\"\n",
    "        return min_res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:\n",
    "        hole = (hole[0], hole[1])\n",
    "        ball = (ball[0], ball[1])\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        \n",
    "        ends = dict()\n",
    "        ends['l'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_left = -1\n",
    "            for j in range(cols):\n",
    "                if maze[i][j]:\n",
    "                    end_left = j\n",
    "                else:\n",
    "                    ends['l'][i][j] = end_left+1\n",
    "        ends['r'] = [[-1]*cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            end_right = cols\n",
    "            for j in range(cols-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_right = j\n",
    "                else:\n",
    "                    ends['r'][i][j] = end_right-1\n",
    "        ends['u'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_up = -1\n",
    "            for i in range(rows):\n",
    "                if maze[i][j]:\n",
    "                    end_up = i\n",
    "                else:\n",
    "                    ends['u'][i][j] = end_up+1\n",
    "        ends['d'] = [[-1]*cols for _ in range(rows)]\n",
    "        for j in range(cols):\n",
    "            end_down = rows\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                if maze[i][j]:\n",
    "                    end_down = i\n",
    "                else:\n",
    "                    ends['d'][i][j] = end_down-1\n",
    "        \n",
    "        global min_length\n",
    "        global min_res\n",
    "        min_length = 1e10\n",
    "        min_res = None\n",
    "        def update_res(length, res):\n",
    "            global min_length\n",
    "            global min_res\n",
    "            if length < min_length:\n",
    "                min_length = length\n",
    "                min_res = res\n",
    "            elif length == min_length and res < min_res:\n",
    "                min_res = res\n",
    "\n",
    "        def recursion(ball, action, path, length, res):\n",
    "            if action == 'd' or action == 'u':\n",
    "                ball_next = (ends[action][ball[0]][ball[1]], ball[1])\n",
    "                if path.get(ball_next,1e10) <= length+abs(ball[0]-ball_next[0]):\n",
    "                    return\n",
    "                res += action\n",
    "                if hole[1] == ball[1] and min(ball[0],ball_next[0]) <= hole[0] <= max(ball[0],ball_next[0]):\n",
    "                    length += abs(ball[0]-hole[0])\n",
    "                    update_res(length, res)\n",
    "                    return\n",
    "                length += abs(ball[0]-ball_next[0])\n",
    "                path[ball_next] = length\n",
    "                if length >= min_length:\n",
    "                    return\n",
    "                for action_next in ['l', 'r']:\n",
    "                    ans = recursion(ball_next, action_next, path, length, res[:])\n",
    "            else:\n",
    "                ball_next = (ball[0], ends[action][ball[0]][ball[1]])\n",
    "                if path.get(ball_next,1e10) <= length+abs(ball[1]-ball_next[1]):\n",
    "                    return\n",
    "                res += action\n",
    "                if hole[0] == ball[0] and min(ball[1],ball_next[1]) <= hole[1] <= max(ball[1],ball_next[1]):\n",
    "                    length += abs(ball[1]-hole[1])\n",
    "                    update_res(length, res)\n",
    "                    return\n",
    "                length += abs(ball[1]-ball_next[1])\n",
    "                path[ball_next] = length\n",
    "                if length >= min_length:\n",
    "                    return\n",
    "                for action_next in ['d', 'u']:\n",
    "                    ans = recursion(ball_next, action_next, path, length, res[:])\n",
    "        for action in ['d', 'l', 'r', 'u']:\n",
    "            recursion(ball, action, {ball:0}, 0, '')\n",
    "        if min_res is None:\n",
    "            return \"impossible\"\n",
    "        return min_res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
